\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}

 \usepackage{graphicx}

 %\usepackage[latin1]{inputenc}

 \usepackage{amsmath, amsthm, amssymb}

 \usepackage{typearea}

 \usepackage{algorithm}

 \usepackage{algorithmic}

 \usepackage{fullpage}

 \usepackage{mathtools}

 \usepackage{multirow}

 \usepackage[all]{xy}

 \addtolength{\voffset}{-30pt}

 \title{Spieltheorie \"Ubung 2}

 \author{Eugen Sawin}

 \renewcommand{\familydefault}{\sfdefault}

 \newcommand{\E}{\mathcal{E}}

 \newcommand{\R}{\mathcal{R}}

 %\include{pythonlisting}

 \pagestyle{empty}

 \begin{document}

 \maketitle

 %

 \section*{Aufgabe 2.1}

 (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^*) = \min_{y\in A_2} \max_{x\in A_1}u_1(x,y)

 \end{align*}

 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}u_1(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.\\\\

 \begin{tabular}{rr|c|c|}

  \multicolumn{2}{r}{}

  & \multicolumn{2}{c}{\emph{Spieler 2}} \\

  \multicolumn{2}{r}{}

  & \multicolumn{1}{c}{$C$}

  & \multicolumn{1}{c}{$D$} \\

  \cline{3-4}

  \multirow{2}{*}{\emph{Spieler 1}}

  & $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)$. \qed

 %

 \section*{Aufgabe 2.3}

 (a) $a_i \in A_i$ ist in G strikt dominiert bedeutet:

 \[\exists{a_i'\in A_i}\forall{a\in A}: u_i(a_{-i},a_i') > u_i(a_{-i},a_i)\]

 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

 \begin{align*}

 U_i(\alpha) &= \sum_{a\in A}\prod_{j\in N}\alpha_j(a_j) \cdot u_i(a)\\

 \text{ und } U_i(\beta) &= \sum_{a\in A}\prod_{j\in N}\beta_j(a_j) \cdot u_i(a)

 \end{align*}

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

 %

 (b) Sei ein $G$ mit folgenden Nutzenfunktionen (in Matrixform) gegeben.\\\\

 \begin{tabular}{rr|c|c|}

  \multicolumn{2}{r}{}

  & \multicolumn{2}{c}{\emph{Spieler 2}} \\

  \multicolumn{2}{r}{}

  & \multicolumn{1}{c}{$D$}

  & \multicolumn{1}{c}{$E$} \\

  \cline{3-4}

  \multirow{2}{*}{\emph{Spieler 1}}

  & $A$ & $2,0$ & $2,0$  \\\cline{3-4}

  & $B$ & $2,0$ & $1,0$ \\\cline{3-4}

  & $C$ & $1,0$ & $2,0$ \\\cline{3-4}

 \end{tabular}\\\\\\

 Wie man leicht erkennen kann, gibt es keine strikt dominierte Strategie in $G$.

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

 %

 (c) Wir haben dies bereits in (a) gezeigt.\\\\

 %

 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.

 \end{document}