sawine@1: \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
sawine@1: \usepackage{graphicx}
sawine@1: %\usepackage[latin1]{inputenc}
sawine@1: \usepackage{amsmath, amsthm, amssymb}
sawine@1: \usepackage{typearea}
sawine@1: \usepackage{algorithm}
sawine@1: \usepackage{algorithmic}
sawine@1: \usepackage{fullpage}
sawine@1: \usepackage{mathtools}
sawine@1: \usepackage{multirow}
sawine@1: \usepackage[all]{xy}
sawine@11: \usepackage{tikz}
sawine@11: \usepackage{tikz-qtree}
sawine@11: \usetikzlibrary{decorations.pathmorphing} % noisy shapes
sawine@11: \usetikzlibrary{fit}					% fitting shapes to coordinates
sawine@11: \usetikzlibrary{backgrounds}	% drawin
sawine@11: \usetikzlibrary{shapes,snakes}
sawine@10: \addtolength{\voffset}{-20pt}
sawine@10: \title{Spieltheorie \"Ubung 4}
sawine@1: \author{Eugen Sawin}
sawine@1: \renewcommand{\familydefault}{\sfdefault}
sawine@1: \newcommand{\E}{\mathcal{E}}
sawine@1: \newcommand{\R}{\mathcal{R}}
sawine@1: 
sawine@1: %\include{pythonlisting}
sawine@1: 
sawine@1: \pagestyle{empty}
sawine@1: \begin{document}
sawine@1: \maketitle
sawine@2: %
sawine@10: \section*{Aufgabe 4.1}
sawine@10: (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.\\\\
sawine@1: \begin{tabular}{rr|c|c|c|c|c|}
sawine@1:  \multicolumn{1}{r}{}
sawine@1:  & \multicolumn{1}{r}{}
sawine@1:  & \multicolumn{5}{c}{\emph{Spieler 2}} \\
sawine@1: 
sawine@1:  \multicolumn{1}{r}{}
sawine@1:  & \multicolumn{1}{r}{}
sawine@10:  & \multicolumn{1}{c}{$p_1$}
sawine@10:  & \multicolumn{1}{c}{$p_2$}
sawine@10:  & \multicolumn{1}{c}{$p_3$}
sawine@10:  & \multicolumn{1}{c}{$p_4$}
sawine@10:  & \multicolumn{1}{c}{$p_5$} \\
sawine@1: 
sawine@1:  \cline{3-7}
sawine@1:  \multirow{5}{*}{\emph{Spieler 1}}
sawine@10:   & $p_1$ & $0,0$    & $1,2$   & $1,3$    & $1,4$   & $1,5$   \\\cline{3-7}
sawine@10:   & $p_2$  & $2,1$    & $0,0$   & $2,3$    & $2,4$   & $2,5$   \\\cline{3-7}
sawine@10:   & $p_3$ & $3,1$    & $3,2$   & $0,0$    & $3,4$   & $3,5$   \\\cline{3-7}
sawine@10:   & $p_4$  & $4,1$    & $4,2$   & $4,3$    & $0,0$   & $4,5$   \\\cline{3-7}
sawine@10:   & $p_5$  & $5,1$    & $5,2$   & $5,3$    & $5,4$   & $0,0$   \\\cline{3-7}
sawine@10: \end{tabular}\\\\\\
sawine@2: %
sawine@10: Seit $(\alpha,\beta)$ ein NG mit Nutzenprofil $(u,v)$ im Spiel $G$, dann ist das LCP durch folgende Ungleichungen definiert.
sawine@3: \begin{align}
sawine@10:   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\\
sawine@10:   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\\
sawine@10:   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\\
sawine@10:   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\\
sawine@10:   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\\
sawine@10:   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\\
sawine@10:   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\\
sawine@10:   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\\
sawine@10:   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\\
sawine@10:   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\\
sawine@10:   0&\leq \alpha(a)&\forall a\in A\\
sawine@10:   0&\leq \beta(b)&\forall b\in B\\
sawine@10:   1&=\alpha(p_1)+\alpha(p_2)+\alpha(p_3)+\alpha(p_4)+\alpha(p_5)\\
sawine@10:   1&=\beta(p_1)+\beta(p_2)+\beta(p_3)+\beta(p_4)+\beta(p_5)\\
sawine@10:   0&=\alpha(a)\cdot(u-U_1(a,\beta))&\forall a\in A\\
sawine@10:   0&=\beta(b)\cdot(v-U_2(\alpha,b))&\forall b\in B
sawine@3: \end{align}
sawine@11: 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.\\\\
sawine@11: %
sawine@11: (b) 
sawine@11: 
sawine@11: \section*{Aufgabe 4.2}
sawine@11: (a) Das extensive Spiel ist $\Gamma=\langle N,H,P,(u_i)_{i\in N}\rangle$ mit 
sawine@11: \begin{align*}
sawine@11:   N&=\{R,E,K\}\\
sawine@11:   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\}\\
sawine@11:   P(h)&=\left\{\begin{array}{l l}
sawine@11:    K, & \text{falls } h=\langle\rangle\\
sawine@11:    R, & \text{falls } h\in\{\langle r\rangle,\langle e,b\rangle,\langle e,h\rangle\}\\
sawine@11:    E, & \text{falls } h\in\{\langle e\rangle,\langle r,b\rangle,\langle r,h\rangle\}\\
sawine@11:                \end{array} \right.\\
sawine@11:  u_R(h)&=\left\{\begin{array}{l l}
sawine@11:   2, &\text{falls } h\in\{\langle r,b,b\rangle,\langle e,b,b\rangle\}\\
sawine@11:   1, &\text{falls } h\in\{\langle r,h,h\rangle,\langle e,h,h\rangle\}\\
sawine@11:   0, &\text{sonst}\\
sawine@11:              \end{array} \right.\\
sawine@11:  u_E(h)&=u_K(h)=\left\{\begin{array}{l l}
sawine@11:   2, &\text{falls } h\in\{\langle r,h,h\rangle,\langle e,h,h\rangle\}\\
sawine@11:   1, &\text{falls } h\in\{\langle r,b,b\rangle,\langle e,b,b\rangle\}\\
sawine@11:   0, &\text{sonst}\\
sawine@11:              \end{array} \right.\\
sawine@11: \end{align*}
sawine@11: Der Spielbaum ist in Abbildung 1 zu sehen.
sawine@11: \begin{figure}[h]
sawine@11: \centering
sawine@11: \tikzstyle{var}=[circle,
sawine@11:   draw=black!100,
sawine@11:   fill=black!0]
sawine@11: \begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
sawine@11:   \matrix[row sep=1.1cm,column sep=0.7cm] {    
sawine@11:     \node(eng)[var]{$eng$}; &\node(spa)[var]{$spa$}; &\node(ukr)[var]{$ukr$}; &\node(nor)[var]{$nor$}; &\node(jap)[var]{$jap$};\\
sawine@11:   \node(red)[var]{$red$}; &\node(gre)[var]{$gre$}; &\node(ivo)[var]{$ivo$}; &\node(yel)[var]{$yel$}; &\node(blu)[var]{$blu$};\\
sawine@11:   \node(dog)[var]{$dog$}; &\node(sna)[var]{$sna$}; &\node(fox)[var]{$fox$}; &\node(hor)[var]{$hor$}; &\node(zeb)[var]{$zeb$};\\
sawine@11:   \node(cof)[var]{$cof$}; &\node(tea)[var]{$tea$}; &\node(mil)[var]{$mil$}; &\node(jui)[var]{$jui$}; &\node(wat)[var]{$wat$};\\
sawine@11:   \node(old)[var]{$old$}; &\node(koo)[var]{$koo$}; &\node(che)[var]{$che$}; &\node(luc)[var]{$luc$}; &\node(par)[var]{$par$};\\
sawine@11:   };
sawine@11:   \path[-]
sawine@11:   (eng) edge (red)
sawine@11:   (spa) edge[bend right=60] (dog)
sawine@11:   (cof) edge (gre)
sawine@11:   (ukr) edge (tea)
sawine@11:   (old) edge (sna)
sawine@11:   (koo) edge (yel)
sawine@11:   (luc) edge (jui)
sawine@11:   (jap) edge[bend left] (par)
sawine@11:   (che) edge[bend left] (fox)
sawine@11:   (yel) edge (hor)
sawine@11:   (nor) edge (blu)
sawine@11:   (gre) edge (ivo)
sawine@11: 
sawine@11:   (eng) edge (spa)
sawine@11:   (eng) edge[bend left] (ukr)
sawine@11:   (eng) edge[bend left] (nor)
sawine@11:   (eng) edge[bend left] (jap)
sawine@11:   (spa) edge (ukr)
sawine@11:   (spa) edge[bend right] (nor)
sawine@11:   (spa) edge[bend right] (jap)
sawine@11:   (ukr) edge (nor)
sawine@11:   (ukr) edge[bend left] (jap)
sawine@11:   (nor) edge (jap)
sawine@11: 
sawine@11:   (red) edge (gre)
sawine@11:   (red) edge[bend left] (ivo)
sawine@11:   (red) edge[bend left] (yel)
sawine@11:   (red) edge[bend left] (blu)
sawine@11:   (gre) edge (ivo)
sawine@11:   (gre) edge[bend right] (yel)
sawine@11:   (gre) edge[bend right] (blu)
sawine@11:   (ivo) edge (yel)
sawine@11:   (ivo) edge[bend left] (blu)
sawine@11:   (yel) edge (blu)
sawine@11:   
sawine@11:   (dog) edge (sna)
sawine@11:   (dog) edge[bend left] (fox)
sawine@11:   (dog) edge[bend left] (hor)
sawine@11:   (dog) edge[bend left] (zeb)
sawine@11:   (sna) edge (fox)
sawine@11:   (sna) edge[bend right] (hor)
sawine@11:   (sna) edge[bend right] (zeb)
sawine@11:   (fox) edge (hor)
sawine@11:   (fox) edge[bend left] (zeb)
sawine@11:   (hor) edge (zeb)
sawine@11: 
sawine@11:   (cof) edge (tea)
sawine@11:   (cof) edge[bend left] (mil)
sawine@11:   (cof) edge[bend left] (jui)
sawine@11:   (cof) edge[bend left] (wat)
sawine@11:   (tea) edge (mil)
sawine@11:   (tea) edge[bend right] (jui)
sawine@11:   (tea) edge[bend right] (wat)
sawine@11:   (mil) edge (jui)
sawine@11:   (mil) edge[bend left] (wat)
sawine@11:   (jui) edge (wat)
sawine@11: 
sawine@11:   (old) edge (koo)
sawine@11:   (old) edge[bend left] (che)
sawine@11:   (old) edge[bend left] (luc)
sawine@11:   (old) edge[bend left] (par)
sawine@11:   (koo) edge (che)
sawine@11:   (koo) edge[bend right] (luc)
sawine@11:   (koo) edge[bend right] (par)
sawine@11:   (che) edge (luc)
sawine@11:   (che) edge[bend left] (par)
sawine@11:   (luc) edge (par)
sawine@11:   ;      
sawine@11: \end{tikzpicture}
sawine@11: \caption{(3.1b) primal constraint graph of $N$}
sawine@11: \end{figure}\\
sawine@11: 
sawine@11: (b) Die Strategien f\"ur Spieler $R$ sind $bbb$, $bbh$, $bhb$, $bhh$, $hbb$, $hbh$, $hhb$ und $hhh$.\\\\
sawine@11: (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.
sawine@11: 
sawine@11: 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.
sawine@11: 
sawine@11: 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.
sawine@11: 
sawine@11: 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^*$.
sawine@11: 
sawine@11: 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^*$.
sawine@11: 
sawine@11: 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^*$.
sawine@11: 
sawine@11: Daraus folgt, dass $s^*=(bbb,hbh,r)$ ein TPG ist.
sawine@1: \end{document}