\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}

\usepackage{graphicx}

%\usepackage[latin1]{inputenc}

\usepackage{amsmath, amsthm, amssymb}

\usepackage{typearea}

\usepackage{algorithm}

\usepackage{algorithmic}

\usepackage{fullpage}

\usepackage{mathtools}

\usepackage{multirow}

\usepackage[all]{xy}

\usepackage{tikz}

\usepackage{tikz-qtree}

\usetikzlibrary{decorations.pathmorphing} % noisy shapes

\usetikzlibrary{fit}					% fitting shapes to coordinates

\usetikzlibrary{backgrounds}	% drawin

\usetikzlibrary{shapes,snakes}

\addtolength{\voffset}{-20pt}

\title{Spieltheorie \"Ubung 4}

\author{Eugen Sawin}

\renewcommand{\familydefault}{\sfdefault}

\newcommand{\E}{\mathcal{E}}

\newcommand{\R}{\mathcal{R}}

%\include{pythonlisting}

\pagestyle{empty}

\begin{document}

\maketitle

%

\section*{Aufgabe 4.1}

(a) Das Picknickspiel ist das Spiel $G=\langle\{1,2\},(A,B),(u_i)\rangle$ mit $A=B=\{p_1,p_2,p_3,p_4,p_5\}$ und das $(u_i)$ definiert durch die folgende Matrix.\\\\

\begin{tabular}{rr|c|c|c|c|c|}

 \multicolumn{1}{r}{}

 & \multicolumn{1}{r}{}

 & \multicolumn{5}{c}{\emph{Spieler 2}} \\

 \multicolumn{1}{r}{}

 & \multicolumn{1}{r}{}

 & \multicolumn{1}{c}{$p_1$}

 & \multicolumn{1}{c}{$p_2$}

 & \multicolumn{1}{c}{$p_3$}

 & \multicolumn{1}{c}{$p_4$}

 & \multicolumn{1}{c}{$p_5$} \\

 \cline{3-7}

 \multirow{5}{*}{\emph{Spieler 1}}

  & $p_1$ & $0,0$    & $1,2$   & $1,3$    & $1,4$   & $1,5$   \\\cline{3-7}

  & $p_2$  & $2,1$    & $0,0$   & $2,3$    & $2,4$   & $2,5$   \\\cline{3-7}

  & $p_3$ & $3,1$    & $3,2$   & $0,0$    & $3,4$   & $3,5$   \\\cline{3-7}

  & $p_4$  & $4,1$    & $4,2$   & $4,3$    & $0,0$   & $4,5$   \\\cline{3-7}

  & $p_5$  & $5,1$    & $5,2$   & $5,3$    & $5,4$   & $0,0$   \\\cline{3-7}

\end{tabular}\\\\\\

%

Seit $(\alpha,\beta)$ ein NG mit Nutzenprofil $(u,v)$ im Spiel $G$, dann ist das LCP durch folgende Ungleichungen definiert.

\begin{align}

  0&\leq u-\beta(p_1)\cdot 0-\beta(p_2)\cdot 1-\beta(p_3)\cdot 1-\beta(p_4)\cdot 1-\beta(p_5)\cdot 1\\

  0&\leq u-\beta(p_1)\cdot 2-\beta(p_2)\cdot 0-\beta(p_3)\cdot 2-\beta(p_4)\cdot 2-\beta(p_5)\cdot 2\\

  0&\leq u-\beta(p_1)\cdot 3-\beta(p_2)\cdot 3-\beta(p_3)\cdot 0-\beta(p_4)\cdot 3-\beta(p_5)\cdot 3\\

  0&\leq u-\beta(p_1)\cdot 4-\beta(p_2)\cdot 4-\beta(p_3)\cdot 4-\beta(p_4)\cdot 0-\beta(p_5)\cdot 4\\

  0&\leq u-\beta(p_1)\cdot 5-\beta(p_2)\cdot 5-\beta(p_3)\cdot 5-\beta(p_4)\cdot 5-\beta(p_5)\cdot 0\\

  0&\leq v-\alpha(p_1)\cdot 0-\alpha(p_2)\cdot 1-\alpha(p_3)\cdot 1-\alpha(p_4)\cdot 1-\alpha(p_5)\cdot 1\\

  0&\leq v-\alpha(p_1)\cdot 2-\alpha(p_2)\cdot 0-\alpha(p_3)\cdot 2-\alpha(p_4)\cdot 2-\alpha(p_5)\cdot 2\\

  0&\leq v-\alpha(p_1)\cdot 3-\alpha(p_2)\cdot 3-\alpha(p_3)\cdot 0-\alpha(p_4)\cdot 3-\alpha(p_5)\cdot 3\\

  0&\leq v-\alpha(p_1)\cdot 4-\alpha(p_2)\cdot 4-\alpha(p_3)\cdot 4-\alpha(p_4)\cdot 0-\alpha(p_5)\cdot 4\\

  0&\leq v-\alpha(p_1)\cdot 5-\alpha(p_2)\cdot 5-\alpha(p_3)\cdot 5-\alpha(p_4)\cdot 5-\alpha(p_5)\cdot 0\\

  0&\leq \alpha(a)&\forall a\in A\\

  0&\leq \beta(b)&\forall b\in B\\

  1&=\alpha(p_1)+\alpha(p_2)+\alpha(p_3)+\alpha(p_4)+\alpha(p_5)\\

  1&=\beta(p_1)+\beta(p_2)+\beta(p_3)+\beta(p_4)+\beta(p_5)\\

  0&=\alpha(a)\cdot(u-U_1(a,\beta))&\forall a\in A\\

  0&=\beta(b)\cdot(v-U_2(\alpha,b))&\forall b\in B

\end{align}

Gleichungen (15) und (16) sind zu expandieren, wie in den Gleichungen (1)-(10) gezeigt. Au\ss erdem m\"ussen f\"ur die Normalform daf\"ur zus\"atzliche Variablen eingef\"uhrt werden. Wir unterlassen beides um die \"Ubersichtlichkeit zu erhalten. Auch (11) und (12) definieren insgesamt 10 Ungleichungen, f\"ur jede Aktion eine.\\\\

%

(b) Da der Tag nur 24 Stunden hat und ich ungerne ad-hoc L\"osungen kreiere, habe ich mich entschieden diese Aufgabe auszulassen und den aufwendigeren, aber ordentlicheren Ansatz f\"ur das Projekt zu verfolgen $(nfg\to game\to LCP\to LP)$.

\section*{Aufgabe 4.2}

(a) Das extensive Spiel ist $\Gamma=\langle N,H,P,(u_i)_{i\in N}\rangle$ mit 

\begin{align*}

  N&=\{R,E,K\}\\

  H&=\{\langle\rangle,\langle r\rangle,\langle e\rangle,\langle r,b\rangle,\langle r,h\rangle,\langle e,b\rangle,\langle e,h\rangle,\langle r,b,b\rangle,\langle r,b,h\rangle,\langle r,h,b\rangle,\langle r,h,h\rangle,\langle e,b,b\rangle,\langle e,b,h\rangle,\langle e,h,b\rangle,\langle e,h,h\rangle\}\\

  P(h)&=\left\{\begin{array}{l l}

   K, & \text{falls } h=\langle\rangle\\

   R, & \text{falls } h\in\{\langle r\rangle,\langle e,b\rangle,\langle e,h\rangle\}\\

   E, & \text{falls } h\in\{\langle e\rangle,\langle r,b\rangle,\langle r,h\rangle\}\\

               \end{array} \right.\\

 u_R(h)&=\left\{\begin{array}{l l}

  2, &\text{falls } h\in\{\langle r,b,b\rangle,\langle e,b,b\rangle\}\\

  1, &\text{falls } h\in\{\langle r,h,h\rangle,\langle e,h,h\rangle\}\\

  0, &\text{sonst}\\

             \end{array} \right.\\

 u_E(h)&=u_K(h)=\left\{\begin{array}{l l}

  2, &\text{falls } h\in\{\langle r,h,h\rangle,\langle e,h,h\rangle\}\\

  1, &\text{falls } h\in\{\langle r,b,b\rangle,\langle e,b,b\rangle\}\\

  0, &\text{sonst}\\

             \end{array} \right.\\

\end{align*}

Der Spielbaum ist in Abbildung 1 zu sehen.

\begin{figure}[h]

\centering

\tikzstyle{var}=[circle,

  draw=black!100,

  fill=black!0]

\tikzstyle{hist}=[rectangle,

  draw=black!100,

  fill=black!0]

\begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]

  \matrix[row sep=1.1cm,column sep=0.1cm] {    

    &&&\node(root)[hist]{$P(\langle\rangle)=K$};\\

    &&\node(r)[hist]{$P(\langle r\rangle)=R$}; &&&\node(e)[hist]{$P(\langle e\rangle)=E$};\\

    &\node(rb)[hist]{$P(\langle r,b\rangle)=E$}; &&\node(rh)[hist]{$P(\langle r,h\rangle)=E$};&\node(eb)[hist]{$P(\langle e,b\rangle)=R$}; &&\node(eh)[hist]{$P(\langle e,h\rangle)=R$};\\

    \node(rbb)[hist]{$\langle r,b,b\rangle$}; &\node(rbh)[hist]{$\langle r,b,h\rangle$}; &\node(rhb)[hist]{$\langle r,h,b\rangle$}; &\node(rhh)[hist]{$\langle r,h,h\rangle$}; &\node(ebb)[hist]{$\langle e,b,b\rangle$}; &\node(ebh)[hist]{$\langle e,b,h\rangle$}; &\node(ehb)[hist]{$\langle e,h,b\rangle$}; &\node(ehh)[hist]{$\langle e,h,h\rangle$};\\

    \node(rbbu)[hist]{$(2,1,1)$}; &\node(rbhu)[hist]{$(0,0,0)$}; &\node(rhbu)[hist]{$(0,0,0)$}; &\node(rhhu)[hist]{$(1,2,2)$}; &\node(ebbu)[hist]{$(2,1,1)$}; &\node(ebhu)[hist]{$(0,0,0)$}; &\node(ehbu)[hist]{$(0,0,0)$}; &\node(ehhu)[hist]{$(1,2,2)$};\\

  };

  \path[-]

  (root) edge node[auto=right]{$r$} (r)

  (root) edge node[auto=left]{$e$} (e)

  (r) edge node[auto=right]{$b$} (rb)

  (r) edge node[auto=left]{$h$} (rh)

  (rb) edge node[auto=right]{$b$} (rbb)

  (rb) edge node[auto=left]{$h$} (rbh)

  (rh) edge node[auto=right]{$b$} (rhb)

  (rh) edge node[auto=left]{$h$} (rhh)

  (e) edge node[auto=right]{$b$} (eb)

  (e) edge node[auto=left]{$h$} (eh)

  (eb) edge node[auto=right]{$b$} (ebb)

  (eb) edge node[auto=left]{$h$} (ebh)

  (eh) edge node[auto=right]{$b$} (ehb)

  (eh) edge node[auto=left]{$h$} (ehh)

  (rbb) edge[dotted] (rbbu)

  (rbh) edge[dotted] (rbhu)

  (rhb) edge[dotted] (rhbu)

  (rhh) edge[dotted] (rhhu)

  (ebb) edge[dotted] (ebbu)

  (ebh) edge[dotted] (ebhu)

  (ehb) edge[dotted] (ehbu)

  (ehh) edge[dotted] (ehhu)

  ;      

\end{tikzpicture}

\caption{(4.2a) Spielbaum von $\Gamma$}

\end{figure}\\

%

(b) Die Strategien f\"ur Spieler $R$ sind $bbb$, $bbh$, $bhb$, $bhh$, $hbb$, $hbh$, $hhb$ und $hhh$.\\\\

(c) Wir geben die Profile als Tupel in der Form $(s_R,s_E,s_K)$, wobei die $s_i$ jeweils die Folge von Aktionen f\"ur Spieler $i$ sind. Analog fassen wir die Auszahlungen in dem Tupel $u(h)=(u_R(h),u_E(h),u_K(h))$ zusammen. Um zu zeigen, dass Aktionsprofil $s^*=(bbb,hbh,r)$ ein TPG ist, reicht es dessen Auszahlung mit derer zu vergleichen, die f\"ur einen Spieler in einer Aktion abweichen.

Wir untersuchen nun alle solche Aktionsprofile, ber\"ucksichtigen dabei jedoch nur solche, die zu einer anderen Auszahlung f\"uhren, d.h. die abweichende Aktion liegt tats\"achlich in dem Ergebnis.

Das Ergebnis $O(s^*)=\langle r,b,b\rangle$ hat die Auszahlungen $u_R(\langle r,b,b\rangle)=2$ und $u_E(\langle r,b,b\rangle)=u_K(\langle r,b,b\rangle)=1$, also $u(O(s^*))=(2,1,1)=u^*$. Wir betrachten nun alle relevanten, abweichenden Aktionsprofile und deren Auszahlungen.

Spieler $R$ kann in $h=\langle r \rangle$ von Aktion $b$ auf $h$ abweichen, was zu dem Aktionsprofil $(hbb,hbh,r)$, dem Ergebnis $O((hbb,hbh,r))=\langle r,h,h\rangle$ und der Auszahlung $u_R(\langle r,h,h\rangle)=1$ f\"uhrt. Wir sehen, dass diese Auszahlung geringer ist, als in $u^*$.

Spieler $E$ kann in $h=\langle r,b\rangle$ von Aktion $b$ auf $h$ abweichen, was zu dem Aktionsprofil $(bbb,hhh,r)$, dem Ergebnis $O((bbb,hhh,r))=\langle r,b,h\rangle$ und der Auszahlung $u_E(\langle r,b,h\rangle)=0$ f\"uhrt. Wir sehen, dass diese Auszahlung geringer ist, als in $u^*$.

Spieler $K$ kann in $h=\langle \rangle$ von Aktion $r$ auf $e$ abweichen, was zu dem Aktionsprofil $(bbb,hbh,e)$, dem Ergebnis $O((bbb,hbh,e))=\langle e,h,b\rangle$ und der Auszahlung $u_K(\langle e,h,b\rangle)=0$ f\"uhrt. Wir sehen, dass diese Auszahlung geringer ist, als in $u^*$.

Daraus folgt, dass $s^*=(bbb,hbh,r)$ ein TPG ist.

\end{document}