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