sawine@1
|
1 |
\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
|
sawine@1
|
2 |
\usepackage{graphicx}
|
sawine@1
|
3 |
%\usepackage[latin1]{inputenc}
|
sawine@1
|
4 |
\usepackage{amsmath, amsthm, amssymb}
|
sawine@1
|
5 |
\usepackage{typearea}
|
sawine@1
|
6 |
\usepackage{algorithm}
|
sawine@1
|
7 |
\usepackage{algorithmic}
|
sawine@1
|
8 |
\usepackage{fullpage}
|
sawine@1
|
9 |
\usepackage{mathtools}
|
sawine@1
|
10 |
\usepackage{multirow}
|
sawine@1
|
11 |
\usepackage[all]{xy}
|
sawine@11
|
12 |
\usepackage{tikz}
|
sawine@11
|
13 |
\usepackage{tikz-qtree}
|
sawine@11
|
14 |
\usetikzlibrary{decorations.pathmorphing} % noisy shapes
|
sawine@11
|
15 |
\usetikzlibrary{fit} % fitting shapes to coordinates
|
sawine@11
|
16 |
\usetikzlibrary{backgrounds} % drawin
|
sawine@11
|
17 |
\usetikzlibrary{shapes,snakes}
|
sawine@10
|
18 |
\addtolength{\voffset}{-20pt}
|
sawine@10
|
19 |
\title{Spieltheorie \"Ubung 4}
|
sawine@1
|
20 |
\author{Eugen Sawin}
|
sawine@1
|
21 |
\renewcommand{\familydefault}{\sfdefault}
|
sawine@1
|
22 |
\newcommand{\E}{\mathcal{E}}
|
sawine@1
|
23 |
\newcommand{\R}{\mathcal{R}}
|
sawine@1
|
24 |
|
sawine@1
|
25 |
%\include{pythonlisting}
|
sawine@1
|
26 |
|
sawine@1
|
27 |
\pagestyle{empty}
|
sawine@1
|
28 |
\begin{document}
|
sawine@1
|
29 |
\maketitle
|
sawine@2
|
30 |
%
|
sawine@10
|
31 |
\section*{Aufgabe 4.1}
|
sawine@10
|
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.\\\\
|
sawine@1
|
33 |
\begin{tabular}{rr|c|c|c|c|c|}
|
sawine@1
|
34 |
\multicolumn{1}{r}{}
|
sawine@1
|
35 |
& \multicolumn{1}{r}{}
|
sawine@1
|
36 |
& \multicolumn{5}{c}{\emph{Spieler 2}} \\
|
sawine@1
|
37 |
|
sawine@1
|
38 |
\multicolumn{1}{r}{}
|
sawine@1
|
39 |
& \multicolumn{1}{r}{}
|
sawine@10
|
40 |
& \multicolumn{1}{c}{$p_1$}
|
sawine@10
|
41 |
& \multicolumn{1}{c}{$p_2$}
|
sawine@10
|
42 |
& \multicolumn{1}{c}{$p_3$}
|
sawine@10
|
43 |
& \multicolumn{1}{c}{$p_4$}
|
sawine@10
|
44 |
& \multicolumn{1}{c}{$p_5$} \\
|
sawine@1
|
45 |
|
sawine@1
|
46 |
\cline{3-7}
|
sawine@1
|
47 |
\multirow{5}{*}{\emph{Spieler 1}}
|
sawine@10
|
48 |
& $p_1$ & $0,0$ & $1,2$ & $1,3$ & $1,4$ & $1,5$ \\\cline{3-7}
|
sawine@10
|
49 |
& $p_2$ & $2,1$ & $0,0$ & $2,3$ & $2,4$ & $2,5$ \\\cline{3-7}
|
sawine@10
|
50 |
& $p_3$ & $3,1$ & $3,2$ & $0,0$ & $3,4$ & $3,5$ \\\cline{3-7}
|
sawine@10
|
51 |
& $p_4$ & $4,1$ & $4,2$ & $4,3$ & $0,0$ & $4,5$ \\\cline{3-7}
|
sawine@10
|
52 |
& $p_5$ & $5,1$ & $5,2$ & $5,3$ & $5,4$ & $0,0$ \\\cline{3-7}
|
sawine@10
|
53 |
\end{tabular}\\\\\\
|
sawine@2
|
54 |
%
|
sawine@10
|
55 |
Seit $(\alpha,\beta)$ ein NG mit Nutzenprofil $(u,v)$ im Spiel $G$, dann ist das LCP durch folgende Ungleichungen definiert.
|
sawine@3
|
56 |
\begin{align}
|
sawine@10
|
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\\
|
sawine@10
|
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\\
|
sawine@10
|
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\\
|
sawine@10
|
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\\
|
sawine@10
|
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\\
|
sawine@10
|
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\\
|
sawine@10
|
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\\
|
sawine@10
|
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\\
|
sawine@10
|
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\\
|
sawine@10
|
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\\
|
sawine@10
|
67 |
0&\leq \alpha(a)&\forall a\in A\\
|
sawine@10
|
68 |
0&\leq \beta(b)&\forall b\in B\\
|
sawine@10
|
69 |
1&=\alpha(p_1)+\alpha(p_2)+\alpha(p_3)+\alpha(p_4)+\alpha(p_5)\\
|
sawine@10
|
70 |
1&=\beta(p_1)+\beta(p_2)+\beta(p_3)+\beta(p_4)+\beta(p_5)\\
|
sawine@10
|
71 |
0&=\alpha(a)\cdot(u-U_1(a,\beta))&\forall a\in A\\
|
sawine@10
|
72 |
0&=\beta(b)\cdot(v-U_2(\alpha,b))&\forall b\in B
|
sawine@3
|
73 |
\end{align}
|
sawine@11
|
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.\\\\
|
sawine@11
|
75 |
%
|
sawine@11
|
76 |
(b)
|
sawine@11
|
77 |
|
sawine@11
|
78 |
\section*{Aufgabe 4.2}
|
sawine@11
|
79 |
(a) Das extensive Spiel ist $\Gamma=\langle N,H,P,(u_i)_{i\in N}\rangle$ mit
|
sawine@11
|
80 |
\begin{align*}
|
sawine@11
|
81 |
N&=\{R,E,K\}\\
|
sawine@11
|
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\}\\
|
sawine@11
|
83 |
P(h)&=\left\{\begin{array}{l l}
|
sawine@11
|
84 |
K, & \text{falls } h=\langle\rangle\\
|
sawine@11
|
85 |
R, & \text{falls } h\in\{\langle r\rangle,\langle e,b\rangle,\langle e,h\rangle\}\\
|
sawine@11
|
86 |
E, & \text{falls } h\in\{\langle e\rangle,\langle r,b\rangle,\langle r,h\rangle\}\\
|
sawine@11
|
87 |
\end{array} \right.\\
|
sawine@11
|
88 |
u_R(h)&=\left\{\begin{array}{l l}
|
sawine@11
|
89 |
2, &\text{falls } h\in\{\langle r,b,b\rangle,\langle e,b,b\rangle\}\\
|
sawine@11
|
90 |
1, &\text{falls } h\in\{\langle r,h,h\rangle,\langle e,h,h\rangle\}\\
|
sawine@11
|
91 |
0, &\text{sonst}\\
|
sawine@11
|
92 |
\end{array} \right.\\
|
sawine@11
|
93 |
u_E(h)&=u_K(h)=\left\{\begin{array}{l l}
|
sawine@11
|
94 |
2, &\text{falls } h\in\{\langle r,h,h\rangle,\langle e,h,h\rangle\}\\
|
sawine@11
|
95 |
1, &\text{falls } h\in\{\langle r,b,b\rangle,\langle e,b,b\rangle\}\\
|
sawine@11
|
96 |
0, &\text{sonst}\\
|
sawine@11
|
97 |
\end{array} \right.\\
|
sawine@11
|
98 |
\end{align*}
|
sawine@11
|
99 |
Der Spielbaum ist in Abbildung 1 zu sehen.
|
sawine@11
|
100 |
\begin{figure}[h]
|
sawine@11
|
101 |
\centering
|
sawine@11
|
102 |
\tikzstyle{var}=[circle,
|
sawine@11
|
103 |
draw=black!100,
|
sawine@11
|
104 |
fill=black!0]
|
sawine@11
|
105 |
\begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
|
sawine@11
|
106 |
\matrix[row sep=1.1cm,column sep=0.7cm] {
|
sawine@11
|
107 |
\node(eng)[var]{$eng$}; &\node(spa)[var]{$spa$}; &\node(ukr)[var]{$ukr$}; &\node(nor)[var]{$nor$}; &\node(jap)[var]{$jap$};\\
|
sawine@11
|
108 |
\node(red)[var]{$red$}; &\node(gre)[var]{$gre$}; &\node(ivo)[var]{$ivo$}; &\node(yel)[var]{$yel$}; &\node(blu)[var]{$blu$};\\
|
sawine@11
|
109 |
\node(dog)[var]{$dog$}; &\node(sna)[var]{$sna$}; &\node(fox)[var]{$fox$}; &\node(hor)[var]{$hor$}; &\node(zeb)[var]{$zeb$};\\
|
sawine@11
|
110 |
\node(cof)[var]{$cof$}; &\node(tea)[var]{$tea$}; &\node(mil)[var]{$mil$}; &\node(jui)[var]{$jui$}; &\node(wat)[var]{$wat$};\\
|
sawine@11
|
111 |
\node(old)[var]{$old$}; &\node(koo)[var]{$koo$}; &\node(che)[var]{$che$}; &\node(luc)[var]{$luc$}; &\node(par)[var]{$par$};\\
|
sawine@11
|
112 |
};
|
sawine@11
|
113 |
\path[-]
|
sawine@11
|
114 |
(eng) edge (red)
|
sawine@11
|
115 |
(spa) edge[bend right=60] (dog)
|
sawine@11
|
116 |
(cof) edge (gre)
|
sawine@11
|
117 |
(ukr) edge (tea)
|
sawine@11
|
118 |
(old) edge (sna)
|
sawine@11
|
119 |
(koo) edge (yel)
|
sawine@11
|
120 |
(luc) edge (jui)
|
sawine@11
|
121 |
(jap) edge[bend left] (par)
|
sawine@11
|
122 |
(che) edge[bend left] (fox)
|
sawine@11
|
123 |
(yel) edge (hor)
|
sawine@11
|
124 |
(nor) edge (blu)
|
sawine@11
|
125 |
(gre) edge (ivo)
|
sawine@11
|
126 |
|
sawine@11
|
127 |
(eng) edge (spa)
|
sawine@11
|
128 |
(eng) edge[bend left] (ukr)
|
sawine@11
|
129 |
(eng) edge[bend left] (nor)
|
sawine@11
|
130 |
(eng) edge[bend left] (jap)
|
sawine@11
|
131 |
(spa) edge (ukr)
|
sawine@11
|
132 |
(spa) edge[bend right] (nor)
|
sawine@11
|
133 |
(spa) edge[bend right] (jap)
|
sawine@11
|
134 |
(ukr) edge (nor)
|
sawine@11
|
135 |
(ukr) edge[bend left] (jap)
|
sawine@11
|
136 |
(nor) edge (jap)
|
sawine@11
|
137 |
|
sawine@11
|
138 |
(red) edge (gre)
|
sawine@11
|
139 |
(red) edge[bend left] (ivo)
|
sawine@11
|
140 |
(red) edge[bend left] (yel)
|
sawine@11
|
141 |
(red) edge[bend left] (blu)
|
sawine@11
|
142 |
(gre) edge (ivo)
|
sawine@11
|
143 |
(gre) edge[bend right] (yel)
|
sawine@11
|
144 |
(gre) edge[bend right] (blu)
|
sawine@11
|
145 |
(ivo) edge (yel)
|
sawine@11
|
146 |
(ivo) edge[bend left] (blu)
|
sawine@11
|
147 |
(yel) edge (blu)
|
sawine@11
|
148 |
|
sawine@11
|
149 |
(dog) edge (sna)
|
sawine@11
|
150 |
(dog) edge[bend left] (fox)
|
sawine@11
|
151 |
(dog) edge[bend left] (hor)
|
sawine@11
|
152 |
(dog) edge[bend left] (zeb)
|
sawine@11
|
153 |
(sna) edge (fox)
|
sawine@11
|
154 |
(sna) edge[bend right] (hor)
|
sawine@11
|
155 |
(sna) edge[bend right] (zeb)
|
sawine@11
|
156 |
(fox) edge (hor)
|
sawine@11
|
157 |
(fox) edge[bend left] (zeb)
|
sawine@11
|
158 |
(hor) edge (zeb)
|
sawine@11
|
159 |
|
sawine@11
|
160 |
(cof) edge (tea)
|
sawine@11
|
161 |
(cof) edge[bend left] (mil)
|
sawine@11
|
162 |
(cof) edge[bend left] (jui)
|
sawine@11
|
163 |
(cof) edge[bend left] (wat)
|
sawine@11
|
164 |
(tea) edge (mil)
|
sawine@11
|
165 |
(tea) edge[bend right] (jui)
|
sawine@11
|
166 |
(tea) edge[bend right] (wat)
|
sawine@11
|
167 |
(mil) edge (jui)
|
sawine@11
|
168 |
(mil) edge[bend left] (wat)
|
sawine@11
|
169 |
(jui) edge (wat)
|
sawine@11
|
170 |
|
sawine@11
|
171 |
(old) edge (koo)
|
sawine@11
|
172 |
(old) edge[bend left] (che)
|
sawine@11
|
173 |
(old) edge[bend left] (luc)
|
sawine@11
|
174 |
(old) edge[bend left] (par)
|
sawine@11
|
175 |
(koo) edge (che)
|
sawine@11
|
176 |
(koo) edge[bend right] (luc)
|
sawine@11
|
177 |
(koo) edge[bend right] (par)
|
sawine@11
|
178 |
(che) edge (luc)
|
sawine@11
|
179 |
(che) edge[bend left] (par)
|
sawine@11
|
180 |
(luc) edge (par)
|
sawine@11
|
181 |
;
|
sawine@11
|
182 |
\end{tikzpicture}
|
sawine@11
|
183 |
\caption{(3.1b) primal constraint graph of $N$}
|
sawine@11
|
184 |
\end{figure}\\
|
sawine@11
|
185 |
|
sawine@11
|
186 |
(b) Die Strategien f\"ur Spieler $R$ sind $bbb$, $bbh$, $bhb$, $bhh$, $hbb$, $hbh$, $hhb$ und $hhh$.\\\\
|
sawine@11
|
187 |
(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
|
188 |
|
sawine@11
|
189 |
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
|
190 |
|
sawine@11
|
191 |
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
|
192 |
|
sawine@11
|
193 |
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
|
194 |
|
sawine@11
|
195 |
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
|
196 |
|
sawine@11
|
197 |
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
|
198 |
|
sawine@11
|
199 |
Daraus folgt, dass $s^*=(bbb,hbh,r)$ ein TPG ist.
|
sawine@1
|
200 |
\end{document}
|