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

 %

 (a) Das Spiel $G = \langle N, (A_i)_{i \in N}, (u_i)_{i \in N} \rangle$ mit $N = \{1,...,n\}$, $A_i = \{K_1, K_2\}$ und 

 \[u_i(a) = \left\{

   \begin{array}{r l}

     1  & \text{wenn } |\{a_i \mid a_i = K_1\}| \geq m \text{ und } i \leq m\\

     1  & \text{wenn } |\{a_i \mid a_i = K_2\}| \geq m \text{ und } i > m\\

     -1 & \text{sonst}\\

   \end{array} \right.

   \]\\

 F\"ur $n = 3$ und $m = 2$ gilt, dass W\"ahler 1 und 2 Kandidat $K_1$ und W\"ahler 3 Kandidat $K_2$ bevorzugen. Wir teilen die ansonsten dreidimensionale Matrix in zwei Matrizen auf. \\\\

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

  \multicolumn{2}{r}{}

  & \multicolumn{2}{c}{\emph{W\"ahler 3 $\rightarrow K_1$}} \\

  \multicolumn{2}{r}{}

  & \multicolumn{2}{c}{\emph{W\"ahler 2}} \\

  \multicolumn{2}{r}{}

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

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

  \cline{3-4}

  \multirow{2}{*}{\emph{W\"ahler 1}}

  & $K_1$ & $1,1,-1$ & $1,1,-1$  \\\cline{3-4}

  & $K_2$ & $1,1,-1$ & $-1,-1,1$ \\\cline{3-4}

 \end{tabular} \\\\\\

 %

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

  \multicolumn{2}{r}{}

  & \multicolumn{2}{c}{\emph{W\"ahler 3 $\rightarrow K_2$}} \\

  \multicolumn{2}{r}{}

  & \multicolumn{2}{c}{\emph{W\"ahler 2}} \\

  \multicolumn{2}{r}{}

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

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

  \cline{3-4}

  \multirow{2}{*}{\emph{W\"ahler 1}}

  & $K_1$ & $1,1,-1$ & $-1,-1,1$  \\\cline{3-4}

  & $K_2$ & $-1,-1,1$ & $-1,-1,1$ \\\cline{3-4}

 \end{tabular} \\\\\\

 %

 (b) $(K_2, *, *)$ wird durch $(K_1, *, *)$ schwach dominiert, da folgendes gilt.

 \begin{align*}

 u_1(K_2, K_1, K_1) &= u_1(K_1, K_1, K_1) \\

 u_1(K_2, K_2, K_1) &< u_1(K_1, K_2, K_1) \\

 u_1(K_2, K_1, K_2) &< u_1(K_1, K_1, K_2) \\

 u_1(K_2, K_2, K_2) &= u_1(K_1, K_2, K_2) \\

 \end{align*}

 %

 $(*, K_2, *)$ wird durch $(*, K_1, *)$ schwach dominiert, da folgendes gilt.

 \begin{align*}

 u_2(K_1, K_2, K_1) &= u_2(K_1, K_1, K_1) \\

 u_2(K_2, K_2, K_1) &< u_2(K_2, K_1, K_1) \\

 u_2(K_1, K_2, K_2) &< u_2(K_1, K_1, K_2) \\

 u_2(K_2, K_2, K_2) &= u_2(K_2, K_1, K_2) \\

 \end{align*}

 %

 $(*, *, K_1)$ wird durch $(*, *, K_2)$ schwach dominiert, da folgendes gilt.

 \begin{align*}

 u_3(K_1, K_1, K_1) &= u_3(K_1, K_1, K_2) \\

 u_3(K_2, K_1, K_1) &< u_3(K_2, K_1, K_2) \\

 u_3(K_1, K_2, K_1) &< u_3(K_1, K_2, K_2) \\

 u_3(K_2, K_2, K_1) &= u_3(K_2, K_2, K_2) \\

 \end{align*}

 Da W\"ahler 1 und 2 Kandidat $K_1$ bevorzugen und W\"aher 3 Kandidat $K_2$ folgt daraus, dass f\"ur den Gegenkandidaten zu stimmen eine schwach dominierte Strategie ist. \\\\

 F\"ur den allgemeinen Fall bedeutet das solange $k_i$ W\"ahler f\"ur $K_i$ stimmen mit $k_i > m$, bleibt die Auszahlung f\"ur alle W\"ahler bei einzelner Strategieabweichung unver\"andert, da danach entweder $k_i - 1 \geq m$ oder $k_i + 1 > m$ gilt und somit die Mehrheit bildet. Da wir den Kandidaten variabel gelassen haben, gilt dies analog f\"ur den Fall mit $k_i < n-m$, da mit $k_i + 1 \leq n - m$ keine Mehrheit gegeben ist.

 Sollten nur $k_i$ W\"ahler f\"ur $K_i$ stimmen mit $k_i = m$, bedeutet jede Strategieabweichung $k_i + 1 > m$ und $k_i - 1 < m$ eine ver\"anderte Auszahlung f\"ur alle W\"ahler. In diesem Fall wird die Auszahlung f\"ur jeden Anh\"anger von Kandidat $K_j$ mit $j \neq i$ erh\"oht, sobald ein W\"ahler mehr f\"ur $K_j$ stimmt, gleichzeitig wird die Auszahlung f\"ur alle Anh\"anger von Kandidat $K_i$ verringert. Analog gilt dies f\"ur den Fall $k_i = m - 1$.

 Aus den beiden F\"allen folgt, dass f\"ur den Gegenkandidaten zu stimmen entweder keine Auswirkung oder eine Verschlechterung der Auszahlung bedeutet und somit eine schwach dominierte Strategie darstellt.\\\\ 

 %

 (c) Die NG des Spiels mit $n = 3$ und $m = 2$ sind $(K_1, K_1, K_1)$, $(K_1, K_1, K_2)$ und $(K_2, K_2, K_2)$.\\\\

 F\"ur den allgemeinen Fall nehmen wir 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.

 F\"ur den Fall dass $k_1$ W\"ahler f\"ur $K_1$ stimmen mit $k_1 = m$, ver\"andert sich die Auszahlung f\"ur alle W\"ahler, sobald ein W\"ahler von $K_1$ auf $K_2$ wechselt. Dieser Fall ist ein NG gdw. W\"ahler 1 bis $m$ f\"ur $K_1$ stimmen, da ein Strategiewechsel f\"ur sie eine Verschlechterung der Auszahlung bedeutet und ein Strategiewechsel der restlichen $n-m$ W\"ahler von $K_2$ auf $K_1$ kein Auswirkung hat. 

 Der andere Fall mit $k_i$ Stimmen f\"ur $K_i$ mit $k_i > m$ ist ein NG, da ein Strategiewechsel eines einzelnen W\"ahlers keine Auswirkung auf die Mehrheitsverteilung und somit die Auszahlungen hat.

 Daraus leiten wir folgende NG f\"ur das Spiel ab. $(w_1,...,w_n)$ mit

 \begin{align}

 &w_i = K_1, 1 \leq i \leq m \text{ und } w_j = K_2, m < j \leq n\\

 &||\{w_i \mid w_i = K_1\}| - |\{w_j \mid w_j = K_2\}|| > 1

 \end{align}

 Umgangssprachlich kann man (1) als den Zusammenhalt der Anh\"anger und (2) als die Dominanz der absoluten Mehrheit bezeichnen. Man beachte, dass (2) kein einzelnes NG definiert, sondern eine Klasse von NG mit ca. $2 (\prod_{i=1}^{n-m-1}(n-i+1)) + 2$ Instanzen.

 \end{document}