1.1 --- a/exercises/solutions/sol02.tex Sun May 13 05:15:33 2012 +0200
1.2 +++ b/exercises/solutions/sol02.tex Mon May 14 02:27:27 2012 +0200
1.3 @@ -71,93 +71,36 @@
1.4 \end{tabular} \\\\\\
1.5 Wir sehen, dass $(A,C)$ ein NG in $G$ ist, jedoch nicht $(B,C)$. \qed
1.6 %
1.7 -\section*{Aufgabe 1.2}
1.8 -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.\\\\
1.9 +\section*{Aufgabe 2.3}
1.10 +(a) $a_i \in A_i$ ist in G strikt dominiert bedeutet:
1.11 +\[\exists{a_i'\in A_i}\forall{a\in A}: u_i(a_{-i},a_i') > u_i(a_{-i},a_i)\]
1.12 +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
1.13 +\begin{align*}
1.14 +U_i(\alpha) &= \sum_{a\in A}\prod_{j\in N}\alpha_j(a_j) \cdot u_i(a)\\
1.15 +\text{ und } U_i(\beta) &= \sum_{a\in A}\prod_{j\in N}\beta_j(a_j) \cdot u_i(a)
1.16 +\end{align*}
1.17 +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\\\\
1.18 %
1.19 -(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
1.20 -\[u_i(a) = \left\{
1.21 - \begin{array}{r l}
1.22 - 1 & \text{wenn } |\{a_i \mid a_i = K_1\}| \geq m \text{ und } i \leq m\\
1.23 - 1 & \text{wenn } |\{a_i \mid a_i = K_2\}| \geq m \text{ und } i > m\\
1.24 - -1 & \text{sonst}\\
1.25 - \end{array} \right.
1.26 - \]\\
1.27 -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. \\\\
1.28 +(b) Sei ein $G$ mit folgenden Nutzenfunktionen (in Matrixform) gegeben.\\\\
1.29 \begin{tabular}{rr|c|c|}
1.30 \multicolumn{2}{r}{}
1.31 - & \multicolumn{2}{c}{\emph{W\"ahler 3 $\rightarrow K_1$}} \\
1.32 + & \multicolumn{2}{c}{\emph{Spieler 2}} \\
1.33
1.34 \multicolumn{2}{r}{}
1.35 - & \multicolumn{2}{c}{\emph{W\"ahler 2}} \\
1.36 -
1.37 - \multicolumn{2}{r}{}
1.38 - & \multicolumn{1}{c}{$K_1$}
1.39 - & \multicolumn{1}{c}{$K_2$} \\
1.40 + & \multicolumn{1}{c}{$D$}
1.41 + & \multicolumn{1}{c}{$E$} \\
1.42
1.43 \cline{3-4}
1.44 - \multirow{2}{*}{\emph{W\"ahler 1}}
1.45 - & $K_1$ & $1,1,-1$ & $1,1,-1$ \\\cline{3-4}
1.46 - & $K_2$ & $1,1,-1$ & $-1,-1,1$ \\\cline{3-4}
1.47 -\end{tabular} \\\\\\
1.48 + \multirow{2}{*}{\emph{Spieler 1}}
1.49 + & $A$ & $2,0$ & $2,0$ \\\cline{3-4}
1.50 + & $B$ & $2,0$ & $1,0$ \\\cline{3-4}
1.51 + & $C$ & $1,0$ & $2,0$ \\\cline{3-4}
1.52 +\end{tabular}\\\\\\
1.53 +Wie man leicht erkennen kann, gibt es keine strikt dominierte Strategie in $G$.
1.54 +
1.55 +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\\\\
1.56 %
1.57 -\begin{tabular}{rr|c|c|}
1.58 - \multicolumn{2}{r}{}
1.59 - & \multicolumn{2}{c}{\emph{W\"ahler 3 $\rightarrow K_2$}} \\
1.60 -
1.61 - \multicolumn{2}{r}{}
1.62 - & \multicolumn{2}{c}{\emph{W\"ahler 2}} \\
1.63 -
1.64 - \multicolumn{2}{r}{}
1.65 - & \multicolumn{1}{c}{$K_1$}
1.66 - & \multicolumn{1}{c}{$K_2$} \\
1.67 -
1.68 - \cline{3-4}
1.69 - \multirow{2}{*}{\emph{W\"ahler 1}}
1.70 - & $K_1$ & $1,1,-1$ & $-1,-1,1$ \\\cline{3-4}
1.71 - & $K_2$ & $-1,-1,1$ & $-1,-1,1$ \\\cline{3-4}
1.72 -\end{tabular} \\\\\\
1.73 +(c) Wir haben dies bereits in (a) gezeigt.\\\\
1.74 %
1.75 -(b) $(K_2, *, *)$ wird durch $(K_1, *, *)$ schwach dominiert, da folgendes gilt.
1.76 -\begin{align*}
1.77 -u_1(K_2, K_1, K_1) &= u_1(K_1, K_1, K_1) \\
1.78 -u_1(K_2, K_2, K_1) &< u_1(K_1, K_2, K_1) \\
1.79 -u_1(K_2, K_1, K_2) &< u_1(K_1, K_1, K_2) \\
1.80 -u_1(K_2, K_2, K_2) &= u_1(K_1, K_2, K_2) \\
1.81 -\end{align*}
1.82 -%
1.83 -$(*, K_2, *)$ wird durch $(*, K_1, *)$ schwach dominiert, da folgendes gilt.
1.84 -\begin{align*}
1.85 -u_2(K_1, K_2, K_1) &= u_2(K_1, K_1, K_1) \\
1.86 -u_2(K_2, K_2, K_1) &< u_2(K_2, K_1, K_1) \\
1.87 -u_2(K_1, K_2, K_2) &< u_2(K_1, K_1, K_2) \\
1.88 -u_2(K_2, K_2, K_2) &= u_2(K_2, K_1, K_2) \\
1.89 -\end{align*}
1.90 -%
1.91 -$(*, *, K_1)$ wird durch $(*, *, K_2)$ schwach dominiert, da folgendes gilt.
1.92 -\begin{align*}
1.93 -u_3(K_1, K_1, K_1) &= u_3(K_1, K_1, K_2) \\
1.94 -u_3(K_2, K_1, K_1) &< u_3(K_2, K_1, K_2) \\
1.95 -u_3(K_1, K_2, K_1) &< u_3(K_1, K_2, K_2) \\
1.96 -u_3(K_2, K_2, K_1) &= u_3(K_2, K_2, K_2) \\
1.97 -\end{align*}
1.98 -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. \\\\
1.99 -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.
1.100 -
1.101 -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$.
1.102 -
1.103 -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.\\\\
1.104 -%
1.105 -(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)$.\\\\
1.106 -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.
1.107 -
1.108 -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.
1.109 -
1.110 -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.
1.111 -
1.112 -Daraus leiten wir folgende NG f\"ur das Spiel ab. $(w_1,...,w_n)$ mit
1.113 -\begin{align}
1.114 -&w_i = K_1, 1 \leq i \leq m \text{ und } w_j = K_2, m < j \leq n\\
1.115 -&||\{w_i \mid w_i = K_1\}| - |\{w_j \mid w_j = K_2\}|| > 1
1.116 -\end{align}
1.117 -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.
1.118 +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.
1.119 \end{document}