\section{Entscheidungstabellen und -bäume}

\subsection{Einleitung}

Die Vorlesung "`Grundlagen des Entscheidens I"' hat das Ziel -- aus
philosophischer Perspektive -- in die Entscheidungs- und Spieltheorie
einzuführen. Dabei geht es vor allem um die Vermittlung von Grundlagen
und elementaren Lösungs- und Rechentechniken, d.h. wir werden
untersuchen, wie man Entscheidungsprobleme als Tabellen oder
Entscheidungsbäume darstellt, wie Entscheidungen unter Risiko (d.h.
bei bekannten Wahrscheinlichkeiten für das Eintreten unbeeinflussbarer
Ereignisse) und unter Unwissen (bei unbekannten Wahrscheinlichkeiten)
getroffen werden können, wie die strategische Interaktion zwischen
mehreren menschlichen Entscheidern mit Hilfe spieltheoretischer
Modelle dargestellt werden kann und vieles mehr. Dabei werden wir uns
immer auch mit den philosophischen Interpretationsfragen dieser
Techniken beschäftigen, sowie mit theoretischen Einwänden, von denen
es zahlreiche gibt.

Ausgespart bleibt in den "`Grundlagen des Entscheidens I"' jedoch
weitgehend die Frage der Anwendung dieser Theorie in verschiedenen
empirischen Wissenschaftsbereichen. Die Anwendbarkeit der Spiel- und
Entscheidungstheorie ist je nach Wissenschaftsbereich mehr oder
weniger stark umstritten. Während sie in der Ökonomie gewissermaßen
kanonisch ist, wird ihr Wert für die Sozial- und Politikwissenschaften
oft bestritten. Besonders die Veröffentlichung von Donald Greens und
Ian Shapiros Buch "`The Pathologies of Rational Choice"'
\cite{green-shapiro:1994}, ein Werk, das die Anwendung ökonomischer
Modelle im Bereich der Politikwissenschaften einer detaillierten und
präzisen Kritik unterzieht, hat eine sehr kontroverse Diskussion über
den Wert und Unwert des ökonomischen Theorieansatzes in den
Politikwissenschaften hervorgerufen. Wenn Zeit bleibt, werden wir am
Ende des Semesters an einem Beispiel untersuchen, worum es bei der
Kritik von Green und Shapiro geht, und aus welchen Gründen die
Anwendung der Spiel- und Entscheidungstheorie sowie das ihr zu Grunde
liegende "`Rational Choice"' Paradigma\footnote{Unter dem "`Rational
  Choice"' Paradigma wird hier die Auffassung verstanden, dass alle
  Menschen strikte Nutzenmaximierer sind, und dass sich sowohl das
  menschliche Handeln als auch gesellschaftliche Strukturen restlos
  und allein aus diesem Prinzip erklären lassen.} außerhalb des
engeren Kreises der Wirtschaftswissenschaften meist zum Scheitern
verurteilt ist.


\subsection{Der Gegenstand der Entscheidungstheorie}

Die Entscheidungstheorie, die in dieser Vorlesung vorgestellt wird,
ist eine
\marginline{Grund\-elemente:\\1.Zustände\\2.Handlungen\\3.Ergebnisse}
formale Theorie davon, wie man in Entscheidungssituationen
bestmögliche Entscheidungen trifft. Eine {\em Entscheidungssituation}
ist dabei charakterisiert durch 1) eine Menge von möglichen
(Welt-){\em Zuständen}, von denen wir entweder nicht wissen, in
welchem dieser möglichen Zustände sich die Welt tatsächlich befindet
(epistemische Unsicherheit), oder bei denen noch nicht feststeht,
welcher Zustand eintreten wird (reale Unsicherheit), 2) eine Menge von
{\em Handlungsalternativen} und 3) eine Menge von {\em Ergebnissen},
deren Realisierung von der gewählten Handlung und dem bestehenden
bzw. dem eingetretenen (Welt-)Zustand abhängt.

Kann man eine bestimmte Entscheidungssituation überhaupt in dieser Form
analysieren, dann lässt sich das Entscheidungsproblem sehr leicht schematisch
in einer Tabelle darstellen: 

\begin{center}
\begin{tabular}{cc|c|c|}
& \multicolumn{1}{c}{} & \multicolumn{2}{c}{{\bf Zustand}} \\
&                  & schwere Klausur   & leichte Klausur    \\ \cline{2-4}
& lernen           & {\em bestehen}    &  {\em bestehen}    \\ \cline{2-4}
\raisebox{1.5ex}[-1.5ex]{{\bf Handlung}} 
& schwimmen gehen  & {\em durchfallen} &  {\em bestehen} \\
\cline{2-4}
\end{tabular}
\end{center}

Die Zeilen repräsentieren in dieser Tabelle unterschiedliche
Handlungs\-alternativ\-en, die Spalten stellen die verschiedenen
Weltzustände dar. Die den Handlungen und Zuständen zugeordneten
Ergebnisse stehen in den entsprechenden Zeilen und Spalten innerhalb
der Tabelle. Diese Tabelle gibt natürlich nur ein äußerst einfaches
Entscheidungsproblem wieder. Ebensogut könnte man sich eine größere
Tabelle mit mehr Handlungsalternativen, z.B. "`lernen und
mitschreiben"', "`schwimmen gehen und mitschreiben"', "`krank
schreiben lassen"', oder mit mehr Zuständen, z.B. "`schwere"',
"`leichte"' und "`mittelschwere Klausur"', vorstellen.
 
Bei der Analyse realer Entscheidungsprobleme stellt es oft eine
Herausforderung \marginline{Das Problem der Problemspezifikation} dar,
alle Zustände und Handlungsalternativen zu identifizieren bzw. eine
geeignete Einteilung dafür zu finden.  Insbesondere dürfen sich die
Handlungsalterantiven untereinander (und ebenso die Zustände
untereinander) nicht überschneiden, das Ergebnis muss eindeutig von
den Handlungen abhängen und es sollten {\em alle} möglichen Zustände
berücksichtigt werden, die Einfluss auf das Ergebnis haben
können. Vergisst man irgendwelche Zustände, die Einfluss auf das
Ergebnis haben können, in der Entscheidungstabelle zu berücksichtigen,
so besteht die Gefahr, dass man unangenehme Überraschungen erlebt,
indem Ergebnisse eintreten, mit denen man nicht gerechnet
hat. Versäumt man umgekehrt, mögliche Handlungsalternativen zu
berücksichtigen, so schränkt man nur die eigene Entscheidungsfreiheit
unnötig ein, wird aber bei ansonsten korrekter Analyse keine
Überraschungen erleben. Mit diesen Schwierigkeiten, die die {\em
  Problemspezifikation} betreffen, werden wir uns in dieser
Vorlesungsreihe jedoch nur am Rande beschäftigen. Es sei jedoch darauf
hingewiesen, dass die korrekte Spezifikation des Entscheidungsproblems
eine hochgradig nicht-triviale Aufgabe sein kann, und dass die
praktische Anwendbarkeit der Entscheidungstheorie auch davon abhängig
ist, ob es in einer gegebenen Situation überhaupt möglich ist, eine
zuverlässige Problemspezifikation im Sinne der Entscheidungstheorie zu
geben.

Abgesehen von den Schwierigkeiten, die sich bei der
Problemspezifikation ergeben \marginline{Systematische Grenzen der
  Anwendbarkeit:} können, ist die Anwendbarkeit der
Entscheidungstheorie aber auch aus systematischen Gründen auf ganz
bestimmte Entscheidungsprobleme eingeschränkt. So kann sie uns
z.B. wenig weiterhelfen, wenn wir uns über die Ergebnisse bzw. die
Bewertung der Ergebnisse einer Entscheidungssituation selbst nicht im
Klaren sind.\marginline{1.Un\-ent\-schlossen\-heit hinsichtlich der
  Zielsetzung} Die Frage, ob jemand im Urlaub lieber ans Meer oder in
die Berge fahren will, stellt ganz sicher ein Entscheidungsprobem dar,
aber es handelt sich nicht um ein Entscheidungsproblem von der Sorte,
bei der uns die Entscheidungstheorie viel weiterhelfen kann. Vielmehr
handelt es sich um ein Problem, bei dem man sich über die eigenen
Präferenzen klar werden muss, man könnte auch sagen: um ein Problem,
bei dem man sich einfach entscheiden muss. In Anlehnung an bestimmte
Doktrinen in der Moralphilosophie bzw. in der politischen Philosophie
könnte man hier vielleicht von einem "`{\em dezisionistischen}
Entscheidungsproblem"' sprechen.

Weiterhin setzt die Entscheidungstheorie voraus, dass wir wissen,
welche möglichen Ergebnisse als Folge der von uns getroffenen
Entscheidungen überhaupt eintreten können.\marginline{2.Unwissenheit
  hinsichtlich der möglichen Ergebnisse} Es gibt aber viele
Situationen, in denen die möglichen Folgen unserer Handlungen für uns
schlicht unabsehbar sind. So können wir zwar absehen, dass sich der
$CO_2$ Gehalt in der Atmosphäre in Zukunft erhöhen wird, wenn wir die
Entscheidung treffen, den $CO_2$ Ausstoß nicht zu verringern, und mit
einer -- allerdings schon erheblich größeren Unsicherheit -- können
uns die Wissenschaftler sagen, dass sich dann das Klima erwärmen wird,
aber wie sich die Erwärmung und die daraus resultierenden klimatischen
Veränderungen gesellschaftlich und politisch auswirken werden, darüber
können wir nur spekulieren. Bei Entscheidungen, bei denen wir die
Menge der möglichen Ergebnisse nicht angeben können, weil wir es dabei
mit "`unknown unknowns"' zu tun haben, stehen wir mit der formalen
Entscheidungstheorie natürlich auf verlorenem Posten. In Bezug auf den
Klimawandel ist daher auch schon der Vorschlag gemacht worden statt
des auf der Entscheidungstheorie fußenden Utilitarismus, verstärkt
einen tugendethischen Ansatz in Anschlag zu bringen \cite[155ff.,
230ff.]{hillerbrand:2006}.\footnote{Da das Buch ansonsten sehr stark
  dem utilitaristischen Ansatz verpflichtet ist, vor allem auch gegen
  die nicht-anthropozentrische Naturethik etwa eines H. Jonas, wird
  man hinter diesem Vorschlag keine grundsätzliche Ablehnung des
  Utilitarismus oder wissenschaftliche Unbedarftheit vermuten dürfen.}

Damit scheiden neben den Entscheidungsproblemen, die aus praktischen
Gründen keine adäquate Problemspezifikation zulassen, viele weitere
wichtige Enscheidungsprobleme aus dem Anwendungsbereich der formalen
Entscheidungstheorie schon von vornherein aus. Es ist wichtig sich
diesen Sachverhalt, dass die Entscheidungstheorie nur einen Teil der
realen Entscheidungsprobleme adäquat behandeln kann, vor Augen zu
halten. Denn dies bedeutet, dass die Entscheidungstheorie, die wir
hier besprechen, nicht notwendigerweise die Theorie der Entscheidungen
schlechthin ist. Oft ist es der Fall, dass wir diejenigen
Entscheidungsprobleme, für die diese Theorie ungeeignet ist, immer
noch im Rahmen anderer, von ihrem Stil her vielleicht ganz
andersartiger Theorien und Ansätze behandeln können, so wie für die
Ethik des Klimaschutzes eine Tugendethik vorgeschlagen worden ist, um
den Schwierigkeiten des Utilitarismus angesichts extremer Unsicherheit
("`unknown unknowns"') zu begegnen.

\marginline{Nachteile des methodenzentrierten Ansatzes} In noch einmal
verschärfter Form stellt sich dasselbe Problem für die Spieltheorie,
deren empirische Anwendungsfälle außerhalb der Ökonomie eher dünn
gesät sind. Die Gefahr besteht daher, dass man durch die einseitige
Konzentration auf solche Probleme, die sich mit Hilfe derartiger
Theorien methodisch in den Griff bekommen lassen, ein völlig falsches
Bild von dem emprischen Sachbereich bekommt, auf den sie sich
beziehen, und von dem sie nur einen kleinen Ausschnitt erfassen
können, der in Wahrheit aber größtenteils ganz anderen Gesetzen
gehorcht. Dass diese Gefahr vornehmlich bei szientistischen, d.h. sich
strenger und formaler Methoden nach dem Vorbild der
Naturwissenschaften bedienender Ansätze auftritt, hängt mit der
Methodenzentriertheit dieser Ansätze zusammen, die dazu führt, dass
vornehmlich solche Probleme als wissenschaftlich relevant ausgewählt
und der Untersuchung für wert befunden werden, die zum vorgegebenen
Methodenkanon passen, anstatt umgekehrt zu gegebenen empirischen
Problemen und Fragestellungen die zur ihrer Behandlung geeigneten
Methoden auszuwählen. A priori sind übrigens der methodenzentrierte
Ansatz und sein Gegenstück, der problemorientierte Ansatz,
gleichermaßen legitim. Nur ist die Gefahr der intellektuellen
Selbsttäuschung beim methodenzentrierten Ansatz offenbar erheblich
größer und tritt daher genau da auf, wo wir sie am wenigsten erwarten
würden, nämlich dort, wo auch das Bewusstsein wissenschaftlicher
Strenge am größten ist.\footnote{Siehe dazu die Kritik von Ian Shapiro
  \cite{shapiro:2005} oder von John Dupré \cite{dupre:2001}, sowie die
  ausführliche Studie von Donald Green und Ian Shapiro
  \cite{green-shapiro:1994}. Besonders das letztere Buch hat eine rege
  Diskussion hervorgerufen. Eine Verteidigung des formalen Rational
  Choice Ansatzes gegen die Kritik von Green und Shapiro hat neben
  anderen Gary W. Cox\cite{cox:1999} unternommen. Cox Ansicht
  allerdings, dass man selbst dann noch theoretische Erfolge für eine
  Theorie reklamieren kann, wenn sie empirisch erfolglos ist
  \cite[S.159-164]{cox:1999}, geht an dem grundlegenden Ziel der
  Wissenschaft vorbei, das selbstverständlich in der Erklärung von
  Vorgängen in der empirischen Welt besteht und nichts anderem, und
  ist eher ein Beispiel wie Wissenschaftlicher sich lieber die
  Wissenschaftstheorie zurechtbiegen als ein Scheitern des von ihnen
  verfolgten Ansatzes einzugestehen. Eine wissenschaftliche Theorie,
  die falsch ist, oder deren Richtigkeit oder Falschheit man nicht
  empirisch feststellen kann, kann man unmöglich "`erfolgreich"'
  nennen.}

Immerhin verbleiben der formalen Entscheidungstheorie aber weite
Bereiche, innerhalb derer wir sie fruchtbar und gewinnbringend
anwenden können. (Und dort wo man sie anwenden kann, ist man mit Hilfe
der Theorie anderen, intuitiven Entscheidungsfindungsmechanismen so
gut wie immer überlegen!) Sofern die Menge der möglichen Ergebnisse
und die Menge der Zustände bekannt ist, können wir sie selbst dann
noch heranziehen, wenn wir nicht einmal wissen, mit welcher
Wahrscheinlichkeit wir mit einem bestimmten Zustand rechnen müssen. In
diesem Fall handelt es sich um "`Entscheidungen unter Unwissen"'. Den
dazugehörigen Teil der Entscheidungstheorie werden wir in der nächsten
und übernächsten Woche besprechen. Sind die Wahrscheinlichkeiten, mit
denen bestimmte Ereignisse eintreten können, dagegen bekannt, dann
spricht man von "`Entscheidungen unter Risiko"'. In diesem Fall lässt
sich die Entscheidungstheorie sogar noch viel besser anwenden, was in
den darauf\/folgenden Wochen demonstriert wird. Was schließlich die
Spieltheorie, die wir als Letztes in diesem Semester ansprechen
werden, von der Entscheidungstheorie unterscheidet, ist, dass sie die
strategische Interaktion zwischen mehreren Entscheidern ("`Spielern"')
untersucht, die wechselseitig aufeinander reagieren bzw. die Reaktion
des Gegenübers antezipieren können. An die Stelle der (Welt-)Zustände
in der Entscheidungstheorie treten in der Spieltheorie also die Züge
des anderen Spielers.

\subsection{Darstellungsformen}

Zum Abschuss dieser Vorlesungsstunde soll -- sozusagen als
"`Appetizer"' -- wenigstens schon ein kurzer Einblick in die
Entscheidungstheorie selbst gegeben werden, mit der wir uns im Laufe
des Semesters eingehend beschäftigen werden. Wir werden im folgenden
Entscheidungsbäume und Entscheidungstabellen als zwei unterschiedliche
Formen der Darstellung von Entscheidungsproblemen kennen lernen und
zeigen, dass sich beide Darstellungsformen wechselseitig ineinander
überführen lassen.

\subsubsection{Entscheidungsbäume und -tabellen}

Zuvor hatten wir schon ein einfaches Beispiel einer
Entscheidungstabelle angeführt. Dies ist nicht die einzige Form, in
der man Entscheidungsprobleme schematisch darstellen kann. Eine
andere, wahrscheinlich sogar anschaulichere Form der schematischen
Darstellung ist der {\em Entscheidungsbaum}. Die weiter oben schon
einmal als Entscheidungstabelle dargestellte Entscheidungssituation
sieht als Baum folgendermaßen aus:

\begin{center} 
\includegraphics[width=12cm]{Grafiken/Beispiel1_1.eps}
\end{center}

Entscheidungsbäume bestehen immer aus Knoten und Ästen.
\marginline{Entscheidungs\-knoten\\~\\ und\\~\\
  Möglich\-keits\-knoten} Dabei werden die\-jenigen Knoten, an denen
eine Entscheidung zwischen unterschiedlichen Handlungsalternativen
getroffen werden muss, {\em Entscheidungs\-knoten}
genannt. Entscheidungsknoten werden durch ein Quadrat
symbolisiert. Diejenigen Knoten, die ein Zufallsereigniss
repräsentieren, werden {\em Möglichkeits\-knoten} genannt und durch
einen Kreis symbolisiert. Eingangs wurde statt von
"`Zufallsereignissen"' von "`Zuständen"' gesprochen. Die Zweige, die
auf einen Entscheidungsknoten folgen, stellen dabei unterschiedliche
"`Handlungsalternativen"' dar, zwischen denen die Entscheiderin wählen
kann.  Die Zweige, die auf einen Möglichkeitsknoten folgen,
entsprechen dagegen unterschiedlichen (Welt)-"'Zuständen"', von denen
entweder nicht sicher ist, welcher davon eintreten wird, oder von
denen wir nicht wissen welcher eintreten wird oder bereits eingetreten
ist, so dass es sich aus Sicht des Entscheiders immer noch um ein
zufälliges Ereignis handelt. (Die Unterscheidung zwischen
epistemischer Unsicherheit und objektiver Unbestimmtheit und, damit
einhergehend, die zwischen subjektiver und objektiver
Wahrscheinlichkeit muss uns an dieser Stelle noch nicht
interessieren.) Die Ergebnisse stehen am Ende der Äste.

\marginline{Umwandlung von Tabellen in Bäume} Hat man eine
Entscheidungssituation, wie in diesem Fall, bereits durch eine
Entscheidungstabelle dargestellt, dann kann man daraus sehr einfach
einen Entscheidungsbaum ableiten, der dieselbe Entscheidungssituation
wiedergibt: Man beginnt mit einem viereckigen Entscheidungsknoten. An
diesen Entscheidungsknoten hängt man alle Handlungsalternativen an,
die in der ersten Spalte der Tabelle stehen. Jeder dieser Zweige wird
dann mit einem runden Möglichkeitsknoten versehen, an den wiederum
alle Zustände angehängt werden, die in der ersten Zeile der Tabelle
stehen. Am Ende der Zweige wird dann das jeweilige Ergebnis aus der
Tabelle eingetragen.

Entscheidungsbäume haben gegenüber Entscheidungstabllen den Vorteil
größerer Anschaulichkeit. Umgekehrt erlauben Tabellen eine kompaktere
Darstellung. Die größere Anschaulichkeit soll an einem weiteren
Beispiel demonstriert werden.  Bei diesem Beispiel geht es um eine
Person, die vor der Entscheidung steht, ob sie an einem Sonntag bei
unsicherer Wetterprognose zur Küste fahren und sich dort entweder
sonnen oder, falls es regnet, dort angeln gehen würde. Die
Entscheidungssituation, die mehrere Einzelentscheidungen beinhaltet
(1) zur Küste fahren oder nicht, 2) bei Regen: Angeln gehen oder
gleich heimkehren) könnte folgendermaßen aussehen:

\begin{center}
\includegraphics[width=12cm]{Grafiken/Beispiel1_2.eps}
\end{center}
(Beispiel aus \cite[S. 18]{resnik:1987})

Entscheidungsbäume erlauben es komplexe Entscheidungen, die aus
mehreren Einzelentscheidungen zusammengesetzt sind, in ihrem Verlauf
darzustellen.  Dennnoch kann man jedes Entscheidungsproblem, dass sich
durch einen Entscheidungsbaum beschreiben lässt auch als
Entscheidungstabelle darstellen.  Dazu muss man die möglichen
Sequenzen von Einzelentscheidungen zu {\em Gesamtstrategien}
zusammenfassen. Solche Gesamtstrategien müssen die "`unter allen
möglichen Eventualitäten"' zu treffenden Einzelentscheidungen
festlegen.  Gleichfalls ist es meist erforderlich, die
Zufallsereignisse zu komplexeren Zuständen zusammenzufassen. Verfährt
man in dieser Weise, dann entsteht aus dem eben präsentierten
Entscheidungsbaum folgende Tabelle:

\begin{center}
\label{AngelnBeispiel}
\input{Grafiken/Beispiel1_3.tex}
\end{center}

\begin{quotation}
\begin{small}
{\em Quizfrage: Kann man anhand dieser Entscheidungstabelle 
 bereits feststellen, welche 
Handlungsalternative gewählt werden
sollte oder zumindest sagen, ob eine bestimmte
Handlungsalternative definitiv nicht gewählt werden sollte?}
\end{small}
\end{quotation}

Nehmen Sie sich ruhig ein wenig Zeit, um sich klar zu machen, dass die
Tabelle dem Entscheidungsbaum entspricht, d.h. dass alle
Handlungsalternativen, die nach der Baumdarstellung gewählt werden
können, auch nach der Tabellendarstellung möglich sind, und ebenso
auch alle denkbaren Kombinationen von Zufallsereignissen. Man könnte
sich dabei zunächst wundern, warum beispielsweise die Kombination der
Ereignisse "`Sonnenschein"' und "`Fische beißen"' nicht in der Tabelle
vorkommt. Aber da in dem Fall, dass die Sonne scheint, der zweite
Möglichkeitsknoten gar nicht mehr erreicht wird, wirkt sich der
Unterschied, ob die Fische beißen oder nicht, auch nicht auf das
Ergebnis aus. Insofern können beide Fälle durch ein- und dieselbe
Zustandsspalte "`Sonnenschein"' erfasst werden

Das Verfahren, wie man einen Entscheidungsbaum in eine Tabelle
überführt, ist ebenfalls rein mechanischer Art. Da es etwas
komplizierter ist als die Umwandlung einer Tabelle in einen
Entscheidungsbaum, werden wir es gleich (Abschnitt \ref{BaumTabelle})
ausführlicher betrachten. Bis dahin soll einfach als gegeben
angenommen werden, dass dies immer möglich ist.

% Die Einzelheiten dieses Verfahrens, das intuitiv sehr
% viel leichter zu erfassen als exakt zu beschreiben ist, müssen uns an dieser
% Stelle nicht interessieren. Ebenso soll an dieser Stelle der Beweis, dass sich
% jeder Entscheidungsbaum in eine Tabelle, die dasselbe Entscheidungsproblem
% ausdrückt, überführen lässt, übergangen werden. (Der Beweis besteht im
% wesentlichen darin, ein Verfahren zur Transformation eines Entscheidungsbaums
% in eine Tabelle anzugeben. Dieser Beweis erfordert keine besonders originellen
% Ideen. Die Kunst besteht jedoch darin, das entsprechende Verfahren exakt zu
% beschreiben; so exakt, dass man es in einen Computer einprogrammieren könnte.
% Wer möchte kann sich ja mal daran versuchen ;) )

Wenn wir es aber einmal als gegeben betrachten, dass man jeden
Entscheidungsbaum in eine Entscheidungstabelle überführen kann, und,
wie zuvor schon gezeigt wurde, jede Entscheidugnstabelle in einen
Entscheidungsbaum, dann hat das die für uns wichtige Konsequenz, dass
wir frei sind, uns je nach Konvenienz der einen oder der anderen
Darstellung zu bedienen. Dies gilt insbesondere für die Entwicklung
der Entscheidungstheorie selbst. Denn wir können nun davon ausgehen,
dass alle Überlegungen, die wir in Bezug auf Entscheidungsprobleme
anhand einer der Darstellungsformen anstellen, ihre Gültigkeit
behalten, wenn wir zu der anderen Darstellungsform übergehen. Für die
Entwicklung der Theorie eignet sich dabei die kompaktere Tabellenform
häufig besser. Umgekehrt bietet sich für die Darstellung und Lösung
bestimmter Entscheidungsprobleme oft eher die anschaulichere
Darstellung durch Entscheidungsbäume eher an.

Wenn die Rede davon war, dass sich Tabellendarstellung und
Baumdarstellung auf mechanische Weise ineinander überführen lassen, so
bedeutet das allerdings nicht, dass wenn man nach diesem Verfahren
einen Entscheidungsbaum zuerst in eine Tabelle und dann wieder in
einen Baum überführt, auch derselbe Entscheidungsbaum wieder dabei
heraus kommt. Transformiert man die eben gewonnene Tabelle wieder in
einen Baum, so hat dieser Entscheidungsbaum die folgende Gestalt:

\begin{center}
\includegraphics[width=12cm]{Grafiken/Beispiel1_4.eps}
\end{center}

Dass der Entscheidungsbaum nach der Übertragung in die Tabellenform und dann
wieder der Rückübertragung in die Baumform ganz anders aussieht, sollte
allerdings nicht verwundern, denn es gibt in der Regel viele unterschiedliche 
Möglichkeiten ein- und dasselbe Entscheidungsproblem als Baum- und Tabelle
darzustellen. Der zuletzt gezeigte Baum stellt in der Tat dasselbe
Entscheidungsproblem dar wie der ursprüngliche Baum. Identisch sind zwei
Entscheidungsprobleme genau dann, wenn denselben Kombinationen von
Handlungsalternativen und Zuständen dieselben Ergebnisse zugeordnet sind. Bei
Entscheidungen unter Risiko müssen die möglichen Weltzustände darüber hinaus
mit denselben Wahrscheinlichkeiten eintreten. Leider kann man weder der
Baumdarstellung noch der Tabellendarstellung unmittelbar ansehen, ob zwei
Entscheidungsprobleme identisch sind. Für die Entscheidungsbäume ist dies nach
dem vorhergehenden Beispiel offensichtlich. Bei Tabellen ergibt sich dies unter
anderem daraus, dass die Reihenfolge der Spalten und Zeilen für das zu Grunde
liegende Entscheidungsproblem egal ist (siehe Aufgabe
\ref{ZeilenSpaltenPermutation}).


\subsubsection{Exkurs: Entscheidungsbäume in Tabellen umwandeln}
\label{BaumTabelle}

{\em Dieses Teilkapitel ist als Exkurs gedacht. Wem es für den Anfang zu
schwierig ist, der kann diesen Exkurs (und die dazu gehörigen Übungsaufgaben) 
ruhig überspringen. Im Folgenden wird darauf nicht mehr zurück gegriffen.}

Um Entscheidungsbäume in Tabellen umzuwandeln, können wir uns den
Umstand zu Nutze machen, dass Entscheidungsbäume, so kompliziert sie
auch sein mögen, aus der Kombination von nur zwei Elementen bestehen,
Entscheidungsknoten und Zufallsknoten. Um einen Entscheidungsbaum in
eine Tabelle zu überführen müssen wir also nur wissen, wie man 1)
Entscheidungsknoten in eine Tabelle überträgt, wie man 2)
Zufallsknoten in eine Tabelle überträgt und 3) wie man einen
komplizierten zusammengesetzten Baum schrittweise mit Hilfe der beiden
vorherigen Übertragungsregeln reduziert.

1) Ein Entscheidungsbaum, der nur aus einem einzigen Ent\-scheidungs\-knoten mit
zwei Alternativen besteht, ergibt eine Tabelle mit zwei Zeilen und einer Spalte:

\vspace{0.5cm}

\parbox{7cm}{Baum:}\parbox{5cm}{Tabelle:}

\vspace{0.25cm}

\parbox{7cm}{\includegraphics[width=6cm]{Grafiken/Beispiel1b_1.eps}}
\parbox{5cm}{
\begin{tabular}{c|c|}
      & $S_1$ \\ \cline{1-2}
$A_1$ & $r_1$ \\ \cline{1-2}
$A_2$ & $r_2$ \\ \cline{1-2}
\end{tabular}}

\vspace{0.5cm}

2) Ein Baum, der nur aus einem Zufallsknoten besteht, liefert demgegenüber eine
Tabelle mit nur einer Zeile und genau soviel Spalten wie Ereignisse an dem
entsprechenden Ereignisknoten eintreten können.

\vspace{0.5cm}

\parbox{7cm}{Baum:}\parbox{5cm}{Tabelle:}

\vspace{0.25cm}

\parbox{7cm}{\includegraphics[width=6cm]{Grafiken/Beispiel1b_2.eps}}
\parbox{5cm}{
\begin{tabular}{c|c|c|}
      & $S_1$ & $S_2$ \\ \cline{1-3}
$A_1$ & $r_1$ & $r_2$ \\ \cline{1-3}
\end{tabular}}

\vspace{0.5cm}

3) Wie kann man nun aber einen Entscheidungsbaum, der aus einer
Vielzahl von Entscheidungs- und Zufallsknoten besteht, in eine Tabelle
überführen? Dazu wird der Baum schrittweise von hinten
"`aufgerollt"'. Die jeweils "`letzten"' Entscheidungs-
bzw. Zufallsknoten von rechts entsprechen genau den vorher
beschriebenen Fällen und können auf die beschriebende Weise
umgewandelt werden.  Kompliziert wird es erst bei den weiter in der
Mitte und am Anfang liegenden Knoten. Wenn wir an einem solchen Knoten
ankommen, haben wir den Baum aber schon soweit aufgerollt, dass wir zu
den sich an den Knoten anschließenden Teilbäumen bereits über Tabellen
verfügen. Das Problem stellt sich also folgendermaßen dar: Wie kann
ein Entscheidungsknoten bzw. ein Zufallsknoten in eine Tabelle
überführt werden, an dessen Enden sich wiederum ganze
Entscheidungsbäume anschließen, für die wir aber immerhin schon über
eine Repräsentation in Tabellenform verfügen?

Um dieses Problem zu lösen, müssen wir wiederum Entscheidungs- und
Zufallsknoten getrennt betrachten:

3 a) Angenommen, wir haben es mit einem Entscheidungsknoten zu tun. Dann endet
der Entscheidungsknoten in zwei Teilbäumen, die bereits als Tabellen
dargestellt sind. Jede dieser Tabellen enthält wiederum eine Menge von
Handlungsalternativen und eine Menge von Zufallsereignissen.

\vspace{0.5cm}

\begin{small}
\parbox{3.5cm}{\ }
\parbox{4.5cm}{\begin{center}Tabelle zu Baum 1\end{center}}
\parbox{4.5cm}{\begin{center}Tabelle zu Baum 2\end{center}}

\parbox{3.5cm}{\includegraphics[width=3.5cm]{Grafiken/Beispiel1b_3.eps}}
\parbox{4.5cm}{
\begin{tabular}{c|ccc|}
         & $S_1$    & $\cdots$ & $S_n$     \\ \cline{1-4}
$A_1$    & $r_{11}$ & $\cdots$ & $r_{1n}$  \\ %\cline{1-4}
$\vdots$ & $\vdots$ & $\ddots$ & $\vdots$  \\ %\cline{1-4}
$A_m$    & $r_{m1}$ & $\cdots$ & $r_{mn}$  \\ \cline{1-4}
\end{tabular}}
\parbox{4.5cm}{
\begin{tabular}{c|ccc|}
         & $T_1$    & $\cdots$ & $T_l$     \\ \cline{1-4}
$B_1$    & $u_{11}$ & $\cdots$ & $u_{1l}$  \\ %\cline{1-4}
$\vdots$ & $\vdots$ & $\ddots$ & $\vdots$  \\ %\cline{1-4}
$B_h$    & $u_{h1}$ & $\cdots$ & $u_{hl}$  \\ \cline{1-4}
\end{tabular}}
\end{small}

\vspace{0.5cm}

Die beiden Ereignismengen $\{S_1, \ldots, S_n\}$ und $\{T_1, \ldots, T_l\}$ des
ersten und des zweiten Teilbaums sowie die entsprechenden Mengen von
Handlungsalternativen $\{A_1, \ldots, A_m\}$ und $\{B_1, \ldots, B_h\}$ müssen
nun in geeigneter Form kobminiert werden, um die Tabelle des gesamten
Entscheidungsknotens aufzubauen. Das geschieht folgendermaßen: In den Spalten
der zusammengefassten Tabelle muss jede mögliche Kombination der
Zufallsereignisse aus beiden Mengen eingetragen werden. In den Zeilen wird als
erstes der Block von Handlungen $X_1 \wedge A_1,\ldots, X_1 \wedge A_m$
eingetragen, worauf als zweites ein Block von Handlungen $X_2 \wedge
B_1,\ldots, X_2 \wedge B_h$ folgt (d.h. jede der Handlungen der ersten Tabelle
wird mit der Handlung $X_1$ kombiniert, jede alternative Handlung der zweiten
Tabelle mit $X_2$).\footnote{Das aus der Logik bekannte Zeichen $\wedge$
bedeutet "`und"', so dass der Ausdruck $X_1 \wedge A_1$ so zu verstehen ist,
dass die Handlung $X_1$ {\em und} die (möglicherweise wiederum aus mehreren
Einzelhandlungen zusammengesetzte) Handlung $A_1$ ausgeführt werden.} Daraus
ergibt sich folgende kombinierte Tabelle:

\begin{small}
\begin{center}
\begin{tabular}{c|ccc|c|ccc|}
                 & $S_1 \wedge T_1$  & $\cdots$ & $S_n \wedge T_1$ & $\cdots$
                 & $S_1 \wedge T_l$  & $\cdots$ & $S_n \wedge T_l$  
                 \\ \cline{1-8} 
$X_1 \wedge A_1$ & $r_{11}$          & $\cdots$ & $r_{1n}$ & $\cdots$ 
                 & $r_{11}$          & $\cdots$ & $r_{1n}$  \\
  $\vdots$       & $\vdots$          & $\ddots$ & $\vdots$ & $\ddots$
                 & $\vdots$          & $\ddots$ & $\vdots$\\
$X_1 \wedge A_m$ & $r_{m1}$          & $\cdots$ & $r_{mn}$ & $\cdots$
                 & $r_{m1}$          & $\cdots$ & $r_{mn}$\\ \cline{1-8}
                   
$X_2 \wedge B_1$ & $u_{11}$          & $\cdots$ & $u_{11}$ & $\cdots$
                 & $u_{1l}$          & $\cdots$ & $u_{1l}$\\
  $\vdots$       & $\vdots$          & $\ddots$ & $\vdots$ & $\ddots$
                 & $\vdots$          & $\ddots$ & $\vdots$\\                  
$X_2 \wedge B_h$ & $u_{h1}$          & $\cdots$ & $u_{h1}$ & $\cdots$
                 & $u_{hl}$          & $\cdots$ & $u_{hl}$\\\cline{1-8}
\end{tabular}
\end{center}
\end{small}

Man beachte: Jedes mögliche Resultat $r_{xy}$ aus der ersten Tabelle kommt genau
$l$-mal vor, d.h. genauso viel mal, wie es Zufallsereignisse in der zweiten
Tabelle gibt. Umgekehrt kommt jedes mögliche Resultat $u_{xy}$ aus der zweiten Tabelle
genau $n$-mal vor, wobei $n$ die Anzahl der Zufallsereignisse in der
ersten Tabelle ist. (Die entsprechende Tabellendarstellung ist also in
der Regel hochgradig redundant und könnte, wenn dies der Fall ist, nachträglich
noch vereinfacht werden.)

\vspace{0.5cm}

3 b) Geht es statt dessen um die Umwandlung eines Zufallsknotens, dann stehen
wir vor der spiegelbildlichen Situation, so dass wir diesmal zwei Spaltenblöcke
bilden und in den Zeilen jede Kombination möglicher Handlungen zu
berücksichtigen haben. 

\vspace{0.5cm}

\begin{small}
\parbox{3.5cm}{\ }
\parbox{4.5cm}{\begin{center}Tabelle zu Baum 1\end{center}}
\parbox{4.5cm}{\begin{center}Tabelle zu Baum 2\end{center}}

\parbox{3.5cm}{\includegraphics[width=3.5cm]{Grafiken/Beispiel1b_4.eps}}
\parbox{4.5cm}{
\begin{tabular}{c|ccc|}
         & $S_1$    & $\cdots$ & $S_n$     \\ \cline{1-4}
$A_1$    & $r_{11}$ & $\cdots$ & $r_{1n}$  \\ %\cline{1-4}
$\vdots$ & $\vdots$ & $\ddots$ & $\vdots$  \\ %\cline{1-4}
$A_m$    & $r_{m1}$ & $\cdots$ & $r_{mn}$  \\ \cline{1-4}
\end{tabular}}
\parbox{4.5cm}{
\begin{tabular}{c|ccc|}
         & $T_1$    & $\cdots$ & $T_l$     \\ \cline{1-4}
$B_1$    & $u_{11}$ & $\cdots$ & $u_{1l}$  \\ %\cline{1-4}
$\vdots$ & $\vdots$ & $\ddots$ & $\vdots$  \\ %\cline{1-4}
$B_h$    & $u_{h1}$ & $\cdots$ & $u_{hl}$  \\ \cline{1-4}
\end{tabular}}
\end{small}

\vspace{0.5cm}

Um die kombinierte Tabelle zu konstruieren, müssen wir also zwei Spaltenblöcke
bilden, wobei der erste Block alle Zufallsereignisse der ersten Tabelle umfasst
(und-verknüpft mit dem Ereignis $Y_1$ versteht sich!) und der zweite Block die
der zweiten Tabelle: In den Zeilen treten alle Kombinationen möglicher
Handlungen auf, und zwar, da die Möglichkeit, eine bestimmte Handlung zu
wählen oder nicht zu wählen erst durch das Eintreten von $Y_1$ oder $Y_2$
überhaupt eröffnet wird, in einer "`wenn\ldots, dann\ldots"'-Form. In einer 
abgekürzten Schreibweise, bei der das Zeichen "`$\rightarrow$"' für die 
wenn-dann-Beziehung stehen soll, schreiben wir also z.B.
$(Y_1 \rightarrow A_2) \wedge (Y_2 \rightarrow B_5)$.\footnote{Angesichts der 
Symmetrie zwischen dem Problem der Umwandlung eines Entscheidungsknotens 
in eine Tabelle und dem der Umwandlung eines
Zufallsknotens in eine Tabelle, könnte es verwundern, dass wir im zweiten Fall
in den Zeilen der generierten Tabelle "`wenn\ldots, dann\ldots"'-Audrücke
vorfinden, während wir uns im ersteren Fall mit simpleren und-Verknüpfungen
begnügen. Dies ist dadurch motiviert, dass wir davon ausgehen, dass die
Ereignisse der Serien $T_1, \ldots, T_n$ bzw. $S_1, \ldots, S_n$ unabhängig von
den getroffenen Entscheidungen auch dann eintreten, wenn sie angesichts des gewählten Zweiges
für das erzielbare Ergebnis nicht mehr relevant sind. Diese Annahme ist
zwar harmlos aber keinesfalls zwingend. Wollte man ganz präzise sein, dann
müsste man die Spaltenüberschriften der aus einem Entscheidungsknoten gewonnen Tabelle
ebenfalls als "`wenn\ldots, dann\ldots"'-Aussagen ausformulieren.}

\begin{small}
\begin{center}
\begin{tabular}{c|ccc|ccc|}
                 & $Y_1 \wedge S_1$  & $\cdots$ & $Y_1 \wedge S_n$
                 & $Y_2 \wedge T_1$  & $\cdots$ & $Y_2 \wedge T_l$  
                 \\ \cline{1-7} 
$Y_1 \rightarrow A_1 \wedge Y_2 \rightarrow B_1$  
                 & $r_{11}$          & $\cdots$ & $r_{1n}$  
                 & $u_{11}$          & $\cdots$ & $u_{1l}$  \\
  $\vdots$       & $\vdots$          & $\ddots$ & $\vdots$ 
                 & $\vdots$          & $\ddots$ & $\vdots$\\
$Y_1 \rightarrow A_1 \wedge Y_2 \rightarrow B_h$     
                 & $r_{11}$          & $\cdots$ & $r_{1n}$ 
                 & $u_{h1}$          & $\cdots$ & $r_{hl}$\\ \cline{1-7}

  $\vdots$       & $\vdots$          & $\ddots$ & $\vdots$ 
                 & $\vdots$          & $\ddots$ & $\vdots$\\ \cline{1-7}
                   
$Y_1 \rightarrow A_m \wedge Y_2 \rightarrow B_1$  
                 & $r_{m1}$          & $\cdots$ & $r_{mn}$  
                 & $u_{11}$          & $\cdots$ & $u_{1l}$  \\
  $\vdots$       & $\vdots$          & $\ddots$ & $\vdots$ 
                 & $\vdots$          & $\ddots$ & $\vdots$\\
$Y_1 \rightarrow A_m \wedge Y_2 \rightarrow B_h$     
                 & $r_{m1}$          & $\cdots$ & $r_{mn}$ 
                 & $u_{h1}$          & $\cdots$ & $r_{hl}$\\ \cline{1-7}
\end{tabular}
\end{center}
\end{small}

Mit diesen beiden "`Übersetzungsregeln"' kann man jeden Entscheidungsbaum
systematisch schrittweise in eine Tabelle überführen. Man ahnt, dass die
Tabelle ziemlich groß werden kann. Dies hängt auch damit zusammen, dass wir an
dieser Stelle auf Sonderfallbetrachtungen verzichtet haben, die die Tabelle
vereinfachen könnten. Z.B. ist es sehr wohl möglich, dass unterschiedliche
Zufallsknoten in einem Baum in Wirklichkeit ein- und dasselbe Ereignis
ausdrücken, nur dass es je nach den zuvor getroffenen Entscheidungen
möglicherweise zu anderen Resultaten führt. Am Beispiel von vorhin lässt sich
dies erläutern:
\begin{center}
\includegraphics[width=8cm]{Grafiken/Beispiel1_1.eps}
\end{center}
Würde man diesen Entscheidungsbaum nach unserem "`mechanischen"' Verfahren in
eine Tabelle überführen, dann würden in den Spaltenüberschriften die Ereignisse
"`schwere Klausur \& schwere Klausur"', "`schwere Klausur \& leichte Klausur"',
"`leichte Klausur \& schwere Klausur"' und "`leichte Klausur \& leichte
Klausur"' stehen. Das hängt damit zusammen, dass der Algorithmus zunächst keine
Informationen darüber hat, ob unterschiedliche Zufallsknoten möglicherweise
identische Zufallsereignisse repräsentieren. Man müsste den
Entscheidungsbaum um entsprechende Informationen ergänzen (z.B. indem man eine
Verbindungslinie zwischen identischen Ereignissen zieht) und den Algorithmus so
anpassen, dass er unmögliche Ereigniskombinationen ("`schwere \& leichte
Klausur"') streicht. 

Weiterhin haben wir den Algorithmus zur Übersetzung von Bäumen in Tabellen
zunächst nur für {\em Binär-}bäume (d.h. Bäume, die an jeder Verzweigung nur
zwei Äste haben) beschrieben. Das ist aber unproblematisch, da man jeden
Entscheidungsbaum in einen binären Entscheidungsbaum umwandeln kann. Z.B. kann
der Entscheidungsbaum
\begin{center}
\includegraphics[width=5cm]{Grafiken/Beispiel1b_5.eps}
\end{center}
einfach in den Baum
\begin{center}
\includegraphics[width=10cm]{Grafiken/Beispiel1b_6.eps}
\end{center}
umgewandelt werden. Eine andere Alternative bestünde darin, den Algorithmus so
anzupassen, dass er sich auch für nicht binäre Entscheidungsbäume eignet
(siehe  Übungsaufgabe \ref{Algorithmusaufgabe} auf Seite
\pageref{Algorithmusaufgabe}).


\subsection{Literaturhinweise}

Zum Schluss ein par Worte zu der Fachliteratur, auf die sich diese Vorlesung
stützt, und die ich als Ergänzung zu diesem Skript als Begeleittexte empfehle:
Zum überwiegenden Teil werde ich in dieser Vorlesung dem Buch "`Choices. An
Introduction to Decision Theory"' von Micheal D. \cite{resnik:1987} folgen. Es
handelt sich dabei um eine didaktisch gut aufbereitete und sehr verständliche
Einführung in die Entscheidungstheorie und die Grundlagen der Spieltheorie.
% Speziell für die Spieltheorie wird auch die Einführung von Martin J. Osborne
% "`An Introduction to Game Theory" \cite{osborne:2004} verwendet.
Für die etwas mathematischeren Teile dieser Vorlesung, insbesondere für den
"`Satz von Arrow"' und die "`Neumann-Morgensternschen Nutzenfunktionen"', möchte
ich auch auf die sehr klare und verständliche Darstellung in dem Lehrbuch von
\cite{mascolell-whinston-green:1995} verweisen. Speziell was die philosophischen
Probleme im Zusammenhang mit der Entscheidungstheorie angeht, werde ich weiterhin
Das Buch von Mark Kaplan "`Decision Theory as Philosophy"' \cite[]{kaplan:1996}
hinzuziehen. Für die Themen aus dem Bereich Social Choice und Public Choicde, 
greife ich unter anderem auf Dennis C. Mueller: "`Public Choice III"'
\cite[]{mueller:2003} zurück. (Als kritische Ergänzung zu der sehr einseitigen
Darstellung Muellers ist, wie bereits erwähnt, das Buch "`The Pathologies of
Rational Choice"' von \cite{green-shapiro:1994}
sehr empfehlenswert.) Soweit in der Vorlesung auch wissenschaftstheoretische Fragen
berührt werden, beziehe ich mich hauptsächlich auf Gerhard Schurz' "`Einführung
in die Wissenschaftstheorie"' \cite[]{schurz:2006}.

