sawine@4: \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
sawine@4: \usepackage{graphicx}
sawine@4: %\usepackage[latin1]{inputenc}
sawine@4: \usepackage{amsmath, amsthm, amssymb}
sawine@4: \usepackage{typearea}
sawine@4: \usepackage{algorithm}
sawine@4: \usepackage{algorithmic}
sawine@4: \usepackage{fullpage}
sawine@4: \usepackage{mathtools}
sawine@4: \usepackage{multirow}
sawine@4: \usepackage[all]{xy}
sawine@5: \addtolength{\voffset}{-30pt}
sawine@4: \title{Spieltheorie \"Ubung 2}
sawine@4: \author{Eugen Sawin}
sawine@4: \renewcommand{\familydefault}{\sfdefault}
sawine@4: \newcommand{\E}{\mathcal{E}}
sawine@4: \newcommand{\R}{\mathcal{R}}
sawine@4: 
sawine@4: %\include{pythonlisting}
sawine@4: 
sawine@4: \pagestyle{empty}
sawine@4: \begin{document}
sawine@4: \maketitle
sawine@4: %
sawine@4: \section*{Aufgabe 2.1}
sawine@5: (a) Sei $(x^*,y^*)$ ein NG in $G=\langle \{1,2\},(A_i),(u_i) \rangle$, dann gilt nach Satz 4
sawine@4: \begin{align*}
sawine@5: u_1(x^*,y^*) = \min_{y\in A_2} \max_{x\in A_1}u_1(x,y)
sawine@4: \end{align*}
sawine@5: 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
sawine@5: \begin{align*}
sawine@5: u_1'(x',y') &= \min_{y\in A_2} \max_{x\in A_1}u_1'(x,y)\\
sawine@5: \iff u_1'(x',y') &= \min_{y\in A_2} \max_{x\in A_1}u_1(x,y) + \alpha_{(x,y)}
sawine@5: \end{align*}
sawine@5: Da $\alpha_a \geq 0$ gilt, folgt daraus
sawine@5: \begin{align*}
sawine@5: 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)\\
sawine@5: \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^*)
sawine@5: \end{align*}
sawine@5: 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\\\\
sawine@4: %
sawine@4: (b) F\"ur jedes NG $(x^*,y^*)$ in G gilt 
sawine@4: \begin{align*}
sawine@5: u_1(x^*,y^*) = \min_{y\in A_2} \max_{x\in A_1}u_1(x,y)
sawine@4: \end{align*}
sawine@5: 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
sawine@5: \begin{align*}
sawine@5: u_1(x',y') = \min_{y\in A_2} \max_{x\in A_1'}u_1(x,y)
sawine@5: \end{align*}
sawine@5: 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
sawine@5: \begin{align*}
sawine@5: 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)\\
sawine@5: \iff u_1(x',y') &\leq u_1(x^*,y^*)  
sawine@5: \end{align*}
sawine@5: 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\\\\
sawine@4: 
sawine@4: \section*{Aufgabe 2.2}
sawine@4: 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.\\\\
sawine@4: \begin{tabular}{rr|c|c|}
sawine@4:  \multicolumn{2}{r}{}
sawine@4:  & \multicolumn{2}{c}{\emph{Spieler 2}} \\
sawine@4: 
sawine@4:  \multicolumn{2}{r}{}
sawine@4:  & \multicolumn{1}{c}{$C$}
sawine@4:  & \multicolumn{1}{c}{$D$} \\
sawine@4: 
sawine@4:  \cline{3-4}
sawine@4:  \multirow{2}{*}{\emph{Spieler 1}}
sawine@4:  & $A$ & $1,-1$ & $2,-2$  \\\cline{3-4}
sawine@4:  & $B$ & $1,-1$ & $-1,1$ \\\cline{3-4}
sawine@4: \end{tabular} \\\\\\
sawine@5: Wir sehen, dass $(A,C)$ ein NG in $G$ ist, jedoch nicht $(B,C)$. \qed
sawine@4: %
sawine@6: \section*{Aufgabe 2.3}
sawine@6: (a) $a_i \in A_i$ ist in G strikt dominiert bedeutet:
sawine@6: \[\exists{a_i'\in A_i}\forall{a\in A}: u_i(a_{-i},a_i') > u_i(a_{-i},a_i)\]
sawine@6: Seien $\alpha_i \in \Delta A_i$ und $\beta_i \in \Delta A_i$ zwei unterschiedliche gemischte Strategien in $G'$, bei den Wahrscheinlichkeitsverteilungen soll gelten $\alpha_i(a_i) > \beta_i(a_i)$. Entsprechend muss dann gelten, dass es ein $a_k \in A_i, a_k \neq a_i$ gibt mit $\alpha_i(a_k) < \beta_i(a_j)$. Es folgt
sawine@6: \begin{align*}
sawine@6: U_i(\alpha) &= \sum_{a\in A}\prod_{j\in N}\alpha_j(a_j) \cdot u_i(a)\\
sawine@6: \text{ und } U_i(\beta) &= \sum_{a\in A}\prod_{j\in N}\beta_j(a_j) \cdot u_i(a)
sawine@6: \end{align*}
sawine@6: Da wir bei $\alpha_i$ die Strategie mit niedrigerer Auszahlung wahrscheinlicher machen, sinkt die Gesamtauszahlung f\"ur Spieler $i$, d.h. $\alpha_i(a_i) \cdot u_i(a_{-i},a_i) + \alpha_i(a_k) \cdot u_i(a_{-k},a_k) < \beta_i(a_i) \cdot u_i(a_{-i},a_i) + \beta_i(a_k) \cdot u_i(a_{-k},a_k)$ und damit folgt $U_i(\alpha) < U_i(\beta)$. Die gemischte Strategie $\alpha_i$ wird also auch in $G'$ strikt dominiert. Mit $\alpha_i(a_i) = 1$, $\beta_i(a_i) = 0$ ansonsten $\alpha_i(a_j) = \beta_i(a_j)$ f\"ur $i \neq j$ folgt, dass $a_i$ strikt dominiert wird in $G'$. \qed\\\\
sawine@4: %
sawine@6: (b) Sei ein $G$ mit folgenden Nutzenfunktionen (in Matrixform) gegeben.\\\\
sawine@4: \begin{tabular}{rr|c|c|}
sawine@4:  \multicolumn{2}{r}{}
sawine@6:  & \multicolumn{2}{c}{\emph{Spieler 2}} \\
sawine@4: 
sawine@4:  \multicolumn{2}{r}{}
sawine@6:  & \multicolumn{1}{c}{$D$}
sawine@6:  & \multicolumn{1}{c}{$E$} \\
sawine@4: 
sawine@4:  \cline{3-4}
sawine@6:  \multirow{2}{*}{\emph{Spieler 1}}
sawine@6:  & $A$ & $2,0$ & $2,0$  \\\cline{3-4}
sawine@6:  & $B$ & $2,0$ & $1,0$ \\\cline{3-4}
sawine@6:  & $C$ & $1,0$ & $2,0$ \\\cline{3-4}
sawine@6: \end{tabular}\\\\\\
sawine@6: Wie man leicht erkennen kann, gibt es keine strikt dominierte Strategie in $G$.
sawine@6: 
sawine@6: Jedoch ist die Auszahlung der gemischten Strategie $\alpha_1$ mit $\alpha_1(A) = 1$, $\alpha_1(B) = \alpha_1(C) = 0$ unabh\"angig von der Verteilung von Spieler 2 strikt besser als jede andere Verteilung f\"ur Spieler 1. Somit ist jede andere gemischte Strategie von $\alpha_1$ strikt dominiert und es folgt, dass Strategien $B$ und $C$ strikt dominiert sind in unserem $G'$. \qed\\\\
sawine@4: %
sawine@6: (c) Wir haben dies bereits in (a) gezeigt.\\\\
sawine@4: %
sawine@6: PS: Bei der Aufgabenl\"osung wurde angenommen, dass mit \emph{stark dominiert} tats\"achlich \emph{strikt dominiert} gemeint war. Dazu wurde die tats\"achliche Definition von strikt dominierten gemischten Strategien eigenst\"andig hergeleitet, da diese nicht im Skript oder Vorlesung definiert worden war.
sawine@4: \end{document}