# HG changeset patch
# User Eugen Sawin <sawine@me73.com>
# Date 1336878933 -7200
# Node ID 31b0bc778f16e136f8145fade1c25543d5cc1263
# Parent  689f616e2a4e7e34595468434540fb19378a77f7
Added some proofs.

diff -r 689f616e2a4e -r 31b0bc778f16 exercises/solutions/sol02.tex
--- a/exercises/solutions/sol02.tex	Sat May 12 20:54:25 2012 +0200
+++ b/exercises/solutions/sol02.tex	Sun May 13 05:15:33 2012 +0200
@@ -9,7 +9,7 @@
 \usepackage{mathtools}
 \usepackage{multirow}
 \usepackage[all]{xy}
-\addtolength{\voffset}{-40pt}
+\addtolength{\voffset}{-30pt}
 \title{Spieltheorie \"Ubung 2}
 \author{Eugen Sawin}
 \renewcommand{\familydefault}{\sfdefault}
@@ -23,32 +23,36 @@
 \maketitle
 %
 \section*{Aufgabe 2.1}
-(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
-\begin{align}
-\forall_{x\in A_1} \min_{y\in A_2} u_1'(x',y) \geq \min_{y \in A_2} u_1'(x,y)
-\end{align}
-Sei $(x^*,y^*)$ ein NG in $G$, dann gilt nach Satz 4.1
-\begin{align}
-\forall_{x\in A_1} \min_{y\in A_2} u_1(x^*,y) \geq \min_{y \in A_2} u_1(x,y)
-\end{align}
-Wir behaupten, dass $u_1'(x',y') < u_1(x^*,y^*)$.\\
-Aus der Problembeschreibung folgt $u_i'(a) = u_i(a) + \alpha_{i,a}$ mit $\alpha_{i,a} \geq 0$. Daraus folgt die Behauptung
+(a) Sei $(x^*,y^*)$ ein NG in $G=\langle \{1,2\},(A_i),(u_i) \rangle$, dann gilt nach Satz 4
 \begin{align*}
-u_1'(x',y') &< u_1'(x^*,y^*) + \alpha_{1,(x^*,y^*)}\\
-\iff u_1'(x',y') &< u_1'(x^*+\alpha_{1,(x^*,y^*)},y^*-\alpha_{1,(x^*,y^*)})\\
+u_1(x^*,y^*) = \min_{y\in A_2} \max_{x\in A_1}u_1(x,y)
 \end{align*}
-\[\forall_{x\in A_1} \min_{y\in A_2} u_1(x^*,y) \geq \min_{y \in A_2} u_1(x,y)\]
-\\\\\setcounter{equation}{0}\\
+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
+\begin{align*}
+u_1'(x',y') &= \min_{y\in A_2} \max_{x\in A_1}u_1'(x,y)\\
+\iff u_1'(x',y') &= \min_{y\in A_2} \max_{x\in A_1}u_1(x,y) + \alpha_{(x,y)}
+\end{align*}
+Da $\alpha_a \geq 0$ gilt, folgt daraus
+\begin{align*}
+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)\\
+\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^*)
+\end{align*}
+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\\\\
 %
 (b) F\"ur jedes NG $(x^*,y^*)$ in G gilt 
 \begin{align*}
-u_1(x^*,y^*) = \min_{y\in A_2} \max_{x\in A_1}(x,y)\\
+u_1(x^*,y^*) = \min_{y\in A_2} \max_{x\in A_1}u_1(x,y)
 \end{align*}
-O.B.d.A streichen wir nun Aktion $d \in A_1$. Es gilt nun
-\begin{align}
-u_1(x^*,y^*) \geq \min_{y\in A_2} \max_{x\in A_1 \setminus \{d\}}(x,y)
-\end{align}
-
+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
+\begin{align*}
+u_1(x',y') = \min_{y\in A_2} \max_{x\in A_1'}u_1(x,y)
+\end{align*}
+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
+\begin{align*}
+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)\\
+\iff u_1(x',y') &\leq u_1(x^*,y^*)  
+\end{align*}
+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\\\\
 
 \section*{Aufgabe 2.2}
 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.\\\\
@@ -65,7 +69,7 @@
  & $A$ & $1,-1$ & $2,-2$  \\\cline{3-4}
  & $B$ & $1,-1$ & $-1,1$ \\\cline{3-4}
 \end{tabular} \\\\\\
-Wir sehen, dass $(A,C)$ ein NG in $G$ ist, jedoch nicht $(B,C)$.
+Wir sehen, dass $(A,C)$ ein NG in $G$ ist, jedoch nicht $(B,C)$. \qed
 %
 \section*{Aufgabe 1.2}
 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.\\\\