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.\\\\