Added final sol04.
1 \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
3 %\usepackage[latin1]{inputenc}
4 \usepackage{amsmath, amsthm, amssymb}
7 \usepackage{algorithmic}
13 \usepackage{tikz-qtree}
14 \usetikzlibrary{decorations.pathmorphing} % noisy shapes
15 \usetikzlibrary{fit} % fitting shapes to coordinates
16 \usetikzlibrary{backgrounds} % drawin
17 \usetikzlibrary{shapes,snakes}
18 \addtolength{\voffset}{-20pt}
19 \title{Spieltheorie \"Ubung 4}
21 \renewcommand{\familydefault}{\sfdefault}
22 \newcommand{\E}{\mathcal{E}}
23 \newcommand{\R}{\mathcal{R}}
25 %\include{pythonlisting}
31 \section*{Aufgabe 4.1}
32 (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.\\\\
33 \begin{tabular}{rr|c|c|c|c|c|}
35 & \multicolumn{1}{r}{}
36 & \multicolumn{5}{c}{\emph{Spieler 2}} \\
39 & \multicolumn{1}{r}{}
40 & \multicolumn{1}{c}{$p_1$}
41 & \multicolumn{1}{c}{$p_2$}
42 & \multicolumn{1}{c}{$p_3$}
43 & \multicolumn{1}{c}{$p_4$}
44 & \multicolumn{1}{c}{$p_5$} \\
47 \multirow{5}{*}{\emph{Spieler 1}}
48 & $p_1$ & $0,0$ & $1,2$ & $1,3$ & $1,4$ & $1,5$ \\\cline{3-7}
49 & $p_2$ & $2,1$ & $0,0$ & $2,3$ & $2,4$ & $2,5$ \\\cline{3-7}
50 & $p_3$ & $3,1$ & $3,2$ & $0,0$ & $3,4$ & $3,5$ \\\cline{3-7}
51 & $p_4$ & $4,1$ & $4,2$ & $4,3$ & $0,0$ & $4,5$ \\\cline{3-7}
52 & $p_5$ & $5,1$ & $5,2$ & $5,3$ & $5,4$ & $0,0$ \\\cline{3-7}
55 Seit $(\alpha,\beta)$ ein NG mit Nutzenprofil $(u,v)$ im Spiel $G$, dann ist das LCP durch folgende Ungleichungen definiert.
57 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\\
58 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\\
59 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\\
60 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\\
61 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\\
62 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\\
63 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\\
64 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\\
65 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\\
66 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\\
67 0&\leq \alpha(a)&\forall a\in A\\
68 0&\leq \beta(b)&\forall b\in B\\
69 1&=\alpha(p_1)+\alpha(p_2)+\alpha(p_3)+\alpha(p_4)+\alpha(p_5)\\
70 1&=\beta(p_1)+\beta(p_2)+\beta(p_3)+\beta(p_4)+\beta(p_5)\\
71 0&=\alpha(a)\cdot(u-U_1(a,\beta))&\forall a\in A\\
72 0&=\beta(b)\cdot(v-U_2(\alpha,b))&\forall b\in B
74 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.\\\\
76 (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)$.
78 \section*{Aufgabe 4.2}
79 (a) Das extensive Spiel ist $\Gamma=\langle N,H,P,(u_i)_{i\in N}\rangle$ mit
82 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\}\\
83 P(h)&=\left\{\begin{array}{l l}
84 K, & \text{falls } h=\langle\rangle\\
85 R, & \text{falls } h\in\{\langle r\rangle,\langle e,b\rangle,\langle e,h\rangle\}\\
86 E, & \text{falls } h\in\{\langle e\rangle,\langle r,b\rangle,\langle r,h\rangle\}\\
88 u_R(h)&=\left\{\begin{array}{l l}
89 2, &\text{falls } h\in\{\langle r,b,b\rangle,\langle e,b,b\rangle\}\\
90 1, &\text{falls } h\in\{\langle r,h,h\rangle,\langle e,h,h\rangle\}\\
93 u_E(h)&=u_K(h)=\left\{\begin{array}{l l}
94 2, &\text{falls } h\in\{\langle r,h,h\rangle,\langle e,h,h\rangle\}\\
95 1, &\text{falls } h\in\{\langle r,b,b\rangle,\langle e,b,b\rangle\}\\
99 Der Spielbaum ist in Abbildung 1 zu sehen.
102 \tikzstyle{var}=[circle,
105 \tikzstyle{hist}=[rectangle,
108 \begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
109 \matrix[row sep=1.1cm,column sep=0.1cm] {
110 &&&\node(root)[hist]{$P(\langle\rangle)=K$};\\
111 &&\node(r)[hist]{$P(\langle r\rangle)=R$}; &&&\node(e)[hist]{$P(\langle e\rangle)=E$};\\
112 &\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$};\\
113 \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$};\\
114 \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)$};\\
117 (root) edge node[auto=right]{$r$} (r)
118 (root) edge node[auto=left]{$e$} (e)
119 (r) edge node[auto=right]{$b$} (rb)
120 (r) edge node[auto=left]{$h$} (rh)
121 (rb) edge node[auto=right]{$b$} (rbb)
122 (rb) edge node[auto=left]{$h$} (rbh)
123 (rh) edge node[auto=right]{$b$} (rhb)
124 (rh) edge node[auto=left]{$h$} (rhh)
125 (e) edge node[auto=right]{$b$} (eb)
126 (e) edge node[auto=left]{$h$} (eh)
127 (eb) edge node[auto=right]{$b$} (ebb)
128 (eb) edge node[auto=left]{$h$} (ebh)
129 (eh) edge node[auto=right]{$b$} (ehb)
130 (eh) edge node[auto=left]{$h$} (ehh)
131 (rbb) edge[dotted] (rbbu)
132 (rbh) edge[dotted] (rbhu)
133 (rhb) edge[dotted] (rhbu)
134 (rhh) edge[dotted] (rhhu)
135 (ebb) edge[dotted] (ebbu)
136 (ebh) edge[dotted] (ebhu)
137 (ehb) edge[dotted] (ehbu)
138 (ehh) edge[dotted] (ehhu)
141 \caption{(4.2a) Spielbaum von $\Gamma$}
144 (b) Die Strategien f\"ur Spieler $R$ sind $bbb$, $bbh$, $bhb$, $bhh$, $hbb$, $hbh$, $hhb$ und $hhh$.\\\\
145 (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.
147 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.
149 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.
151 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^*$.
153 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^*$.
155 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^*$.
157 Daraus folgt, dass $s^*=(bbb,hbh,r)$ ein TPG ist.