Added some proofs.
1.1 --- a/exercises/solutions/sol02.tex Sat May 12 20:54:25 2012 +0200
1.2 +++ b/exercises/solutions/sol02.tex Sun May 13 05:15:33 2012 +0200
1.3 @@ -9,7 +9,7 @@
1.4 \usepackage{mathtools}
1.5 \usepackage{multirow}
1.6 \usepackage[all]{xy}
1.7 -\addtolength{\voffset}{-40pt}
1.8 +\addtolength{\voffset}{-30pt}
1.9 \title{Spieltheorie \"Ubung 2}
1.10 \author{Eugen Sawin}
1.11 \renewcommand{\familydefault}{\sfdefault}
1.12 @@ -23,32 +23,36 @@
1.13 \maketitle
1.14 %
1.15 \section*{Aufgabe 2.1}
1.16 -(a) Sei $G = \langle \{1,2\},(A_i),(u_i) \rangle$ und $(x',y')$ ein NG in $G' = \langle \{1,2\},(A_i),(u_i') \rangle$, dann gilt nach Satz 4.1
1.17 -\begin{align}
1.18 -\forall_{x\in A_1} \min_{y\in A_2} u_1'(x',y) \geq \min_{y \in A_2} u_1'(x,y)
1.19 -\end{align}
1.20 -Sei $(x^*,y^*)$ ein NG in $G$, dann gilt nach Satz 4.1
1.21 -\begin{align}
1.22 -\forall_{x\in A_1} \min_{y\in A_2} u_1(x^*,y) \geq \min_{y \in A_2} u_1(x,y)
1.23 -\end{align}
1.24 -Wir behaupten, dass $u_1'(x',y') < u_1(x^*,y^*)$.\\
1.25 -Aus der Problembeschreibung folgt $u_i'(a) = u_i(a) + \alpha_{i,a}$ mit $\alpha_{i,a} \geq 0$. Daraus folgt die Behauptung
1.26 +(a) Sei $(x^*,y^*)$ ein NG in $G=\langle \{1,2\},(A_i),(u_i) \rangle$, dann gilt nach Satz 4
1.27 \begin{align*}
1.28 -u_1'(x',y') &< u_1'(x^*,y^*) + \alpha_{1,(x^*,y^*)}\\
1.29 -\iff u_1'(x',y') &< u_1'(x^*+\alpha_{1,(x^*,y^*)},y^*-\alpha_{1,(x^*,y^*)})\\
1.30 +u_1(x^*,y^*) = \min_{y\in A_2} \max_{x\in A_1}u_1(x,y)
1.31 \end{align*}
1.32 -\[\forall_{x\in A_1} \min_{y\in A_2} u_1(x^*,y) \geq \min_{y \in A_2} u_1(x,y)\]
1.33 -\\\\\setcounter{equation}{0}\\
1.34 +Aus der Problembeschreibung folgt ein $G'=\langle \{1,2\},(A_i),(u_i')\rangle$ mit $u_1'(a)=u_1(a) + \alpha_a$ und $u_2'(a)=u_2(a)-\alpha_a$ mit $\alpha_a \geq 0$. $\alpha_a$ ist die Nutzwerterh\"ohung f\"ur Spieler 1 in Aktionsprofil $a$. Daraus folgt, dass f\"ur jedes NG $(x',y')$ in $G'$ folgendes gilt
1.35 +\begin{align*}
1.36 +u_1'(x',y') &= \min_{y\in A_2} \max_{x\in A_1}u_1'(x,y)\\
1.37 +\iff u_1'(x',y') &= \min_{y\in A_2} \max_{x\in A_1}u_1(x,y) + \alpha_{(x,y)}
1.38 +\end{align*}
1.39 +Da $\alpha_a \geq 0$ gilt, folgt daraus
1.40 +\begin{align*}
1.41 +u_1'(x',y') &= \min_{y\in A_2} \max_{x\in A_1}u_1(x,y) + \alpha_{(x,y)} \geq \min_{y\in A_2} \max_{x\in A_1}u_1(x,y)\\
1.42 +\iff u_1'(x',y') &= \min_{y\in A_2} \max_{x\in A_1}u_1(x,y) + \alpha_{(x,y)} \geq u_1(x^*,y^*)
1.43 +\end{align*}
1.44 +Somit gilt $u_1'(x',y') \geq u_1(x^*,y^*)$ f\"ur jedes NG $(x',y')$ in $G'$ und $(x^*,y^*)$ in $G$. \qed\\\\
1.45 %
1.46 (b) F\"ur jedes NG $(x^*,y^*)$ in G gilt
1.47 \begin{align*}
1.48 -u_1(x^*,y^*) = \min_{y\in A_2} \max_{x\in A_1}(x,y)\\
1.49 +u_1(x^*,y^*) = \min_{y\in A_2} \max_{x\in A_1}u_1(x,y)
1.50 \end{align*}
1.51 -O.B.d.A streichen wir nun Aktion $d \in A_1$. Es gilt nun
1.52 -\begin{align}
1.53 -u_1(x^*,y^*) \geq \min_{y\in A_2} \max_{x\in A_1 \setminus \{d\}}(x,y)
1.54 -\end{align}
1.55 -
1.56 +O.B.d.A streichen wir nun Aktion $d \in A_1$ in dem Spiel $G'$. Sei $A_1' = A_1 \setminus \{d\}$. F\"ur jedes NG $(x',y')$ in $G'$ gilt nun
1.57 +\begin{align*}
1.58 +u_1(x',y') = \min_{y\in A_2} \max_{x\in A_1'}u_1(x,y)
1.59 +\end{align*}
1.60 +Aus den beiden F\"allen $\max_{x\in A_1'}u_1(x,y) < u_1(d,y)$ f\"ur ein $y \in A_2$, und $\max_{x\in A_1'}u_1(x,y) = u_1(d,y)$ folgt
1.61 +\begin{align*}
1.62 +u_1(x',y') &= \min_{y\in A_2} \max_{x\in A_1'}u_1(x,y) \leq \min_{y\in A_2} \max_{x\in A_1}u_1(x,y)\\
1.63 +\iff u_1(x',y') &\leq u_1(x^*,y^*)
1.64 +\end{align*}
1.65 +Den Fall $\max_{x\in A_1'}u_1(x,y) > u_1(d,y)$ kann es nicht geben, da dann gilt $\exists{y,y' \in A_2, x \in A_1, x'\in A_1'}: u_1(x',y') > u_1(x,y) \implies x' \notin A_1$, was in Widerspruch steht zu $A_1' = A_1 \setminus \{d\} \implies A_1' \subset A_1$. \qed\\\\
1.66
1.67 \section*{Aufgabe 2.2}
1.68 Wir zeigen folgendes Gegenbeispiel mit Spiel $G = \langle \{1,2\}, (A_i), (u_i) \rangle$, mit $A_1 = \{A,B\}$, $A_2 = \{C,D\}$, $u_i$ ist durch die folgende Matrix definiert.\\\\
1.69 @@ -65,7 +69,7 @@
1.70 & $A$ & $1,-1$ & $2,-2$ \\\cline{3-4}
1.71 & $B$ & $1,-1$ & $-1,1$ \\\cline{3-4}
1.72 \end{tabular} \\\\\\
1.73 -Wir sehen, dass $(A,C)$ ein NG in $G$ ist, jedoch nicht $(B,C)$.
1.74 +Wir sehen, dass $(A,C)$ ein NG in $G$ ist, jedoch nicht $(B,C)$. \qed
1.75 %
1.76 \section*{Aufgabe 1.2}
1.77 Wir nehmen o.B.d.A. an, dass W\"ahler 1 bis $m$ Kandidat $K_1$ bevorzugen und die W\"ahler $m + 1$ bis $n$ Kandidat $K_2$. Zudem soll immer $i \neq j$ gelten.\\\\