sawine@4
|
1 |
\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
|
sawine@4
|
2 |
\usepackage{graphicx}
|
sawine@4
|
3 |
%\usepackage[latin1]{inputenc}
|
sawine@4
|
4 |
\usepackage{amsmath, amsthm, amssymb}
|
sawine@4
|
5 |
\usepackage{typearea}
|
sawine@4
|
6 |
\usepackage{algorithm}
|
sawine@4
|
7 |
\usepackage{algorithmic}
|
sawine@4
|
8 |
\usepackage{fullpage}
|
sawine@4
|
9 |
\usepackage{mathtools}
|
sawine@4
|
10 |
\usepackage{multirow}
|
sawine@4
|
11 |
\usepackage[all]{xy}
|
sawine@5
|
12 |
\addtolength{\voffset}{-30pt}
|
sawine@4
|
13 |
\title{Spieltheorie \"Ubung 2}
|
sawine@4
|
14 |
\author{Eugen Sawin}
|
sawine@4
|
15 |
\renewcommand{\familydefault}{\sfdefault}
|
sawine@4
|
16 |
\newcommand{\E}{\mathcal{E}}
|
sawine@4
|
17 |
\newcommand{\R}{\mathcal{R}}
|
sawine@4
|
18 |
|
sawine@4
|
19 |
%\include{pythonlisting}
|
sawine@4
|
20 |
|
sawine@4
|
21 |
\pagestyle{empty}
|
sawine@4
|
22 |
\begin{document}
|
sawine@4
|
23 |
\maketitle
|
sawine@4
|
24 |
%
|
sawine@4
|
25 |
\section*{Aufgabe 2.1}
|
sawine@5
|
26 |
(a) Sei $(x^*,y^*)$ ein NG in $G=\langle \{1,2\},(A_i),(u_i) \rangle$, dann gilt nach Satz 4
|
sawine@4
|
27 |
\begin{align*}
|
sawine@5
|
28 |
u_1(x^*,y^*) = \min_{y\in A_2} \max_{x\in A_1}u_1(x,y)
|
sawine@4
|
29 |
\end{align*}
|
sawine@5
|
30 |
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
|
31 |
\begin{align*}
|
sawine@5
|
32 |
u_1'(x',y') &= \min_{y\in A_2} \max_{x\in A_1}u_1'(x,y)\\
|
sawine@5
|
33 |
\iff u_1'(x',y') &= \min_{y\in A_2} \max_{x\in A_1}u_1(x,y) + \alpha_{(x,y)}
|
sawine@5
|
34 |
\end{align*}
|
sawine@5
|
35 |
Da $\alpha_a \geq 0$ gilt, folgt daraus
|
sawine@5
|
36 |
\begin{align*}
|
sawine@5
|
37 |
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
|
38 |
\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
|
39 |
\end{align*}
|
sawine@5
|
40 |
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
|
41 |
%
|
sawine@4
|
42 |
(b) F\"ur jedes NG $(x^*,y^*)$ in G gilt
|
sawine@4
|
43 |
\begin{align*}
|
sawine@5
|
44 |
u_1(x^*,y^*) = \min_{y\in A_2} \max_{x\in A_1}u_1(x,y)
|
sawine@4
|
45 |
\end{align*}
|
sawine@5
|
46 |
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
|
47 |
\begin{align*}
|
sawine@5
|
48 |
u_1(x',y') = \min_{y\in A_2} \max_{x\in A_1'}u_1(x,y)
|
sawine@5
|
49 |
\end{align*}
|
sawine@5
|
50 |
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
|
51 |
\begin{align*}
|
sawine@5
|
52 |
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
|
53 |
\iff u_1(x',y') &\leq u_1(x^*,y^*)
|
sawine@5
|
54 |
\end{align*}
|
sawine@5
|
55 |
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
|
56 |
|
sawine@4
|
57 |
\section*{Aufgabe 2.2}
|
sawine@4
|
58 |
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
|
59 |
\begin{tabular}{rr|c|c|}
|
sawine@4
|
60 |
\multicolumn{2}{r}{}
|
sawine@4
|
61 |
& \multicolumn{2}{c}{\emph{Spieler 2}} \\
|
sawine@4
|
62 |
|
sawine@4
|
63 |
\multicolumn{2}{r}{}
|
sawine@4
|
64 |
& \multicolumn{1}{c}{$C$}
|
sawine@4
|
65 |
& \multicolumn{1}{c}{$D$} \\
|
sawine@4
|
66 |
|
sawine@4
|
67 |
\cline{3-4}
|
sawine@4
|
68 |
\multirow{2}{*}{\emph{Spieler 1}}
|
sawine@4
|
69 |
& $A$ & $1,-1$ & $2,-2$ \\\cline{3-4}
|
sawine@4
|
70 |
& $B$ & $1,-1$ & $-1,1$ \\\cline{3-4}
|
sawine@4
|
71 |
\end{tabular} \\\\\\
|
sawine@5
|
72 |
Wir sehen, dass $(A,C)$ ein NG in $G$ ist, jedoch nicht $(B,C)$. \qed
|
sawine@4
|
73 |
%
|
sawine@6
|
74 |
\section*{Aufgabe 2.3}
|
sawine@6
|
75 |
(a) $a_i \in A_i$ ist in G strikt dominiert bedeutet:
|
sawine@6
|
76 |
\[\exists{a_i'\in A_i}\forall{a\in A}: u_i(a_{-i},a_i') > u_i(a_{-i},a_i)\]
|
sawine@6
|
77 |
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
|
78 |
\begin{align*}
|
sawine@6
|
79 |
U_i(\alpha) &= \sum_{a\in A}\prod_{j\in N}\alpha_j(a_j) \cdot u_i(a)\\
|
sawine@6
|
80 |
\text{ und } U_i(\beta) &= \sum_{a\in A}\prod_{j\in N}\beta_j(a_j) \cdot u_i(a)
|
sawine@6
|
81 |
\end{align*}
|
sawine@6
|
82 |
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
|
83 |
%
|
sawine@6
|
84 |
(b) Sei ein $G$ mit folgenden Nutzenfunktionen (in Matrixform) gegeben.\\\\
|
sawine@4
|
85 |
\begin{tabular}{rr|c|c|}
|
sawine@4
|
86 |
\multicolumn{2}{r}{}
|
sawine@6
|
87 |
& \multicolumn{2}{c}{\emph{Spieler 2}} \\
|
sawine@4
|
88 |
|
sawine@4
|
89 |
\multicolumn{2}{r}{}
|
sawine@6
|
90 |
& \multicolumn{1}{c}{$D$}
|
sawine@6
|
91 |
& \multicolumn{1}{c}{$E$} \\
|
sawine@4
|
92 |
|
sawine@4
|
93 |
\cline{3-4}
|
sawine@6
|
94 |
\multirow{2}{*}{\emph{Spieler 1}}
|
sawine@6
|
95 |
& $A$ & $2,0$ & $2,0$ \\\cline{3-4}
|
sawine@6
|
96 |
& $B$ & $2,0$ & $1,0$ \\\cline{3-4}
|
sawine@6
|
97 |
& $C$ & $1,0$ & $2,0$ \\\cline{3-4}
|
sawine@6
|
98 |
\end{tabular}\\\\\\
|
sawine@6
|
99 |
Wie man leicht erkennen kann, gibt es keine strikt dominierte Strategie in $G$.
|
sawine@6
|
100 |
|
sawine@6
|
101 |
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
|
102 |
%
|
sawine@6
|
103 |
(c) Wir haben dies bereits in (a) gezeigt.\\\\
|
sawine@4
|
104 |
%
|
sawine@6
|
105 |
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
|
106 |
\end{document}
|