sawine@7
|
1 |
\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
|
sawine@7
|
2 |
\usepackage{graphicx}
|
sawine@7
|
3 |
%\usepackage[latin1]{inputenc}
|
sawine@7
|
4 |
\usepackage{amsmath, amsthm, amssymb}
|
sawine@7
|
5 |
\usepackage{typearea}
|
sawine@7
|
6 |
\usepackage{algorithm}
|
sawine@7
|
7 |
\usepackage{algorithmic}
|
sawine@7
|
8 |
\usepackage{fullpage}
|
sawine@7
|
9 |
\usepackage{mathtools}
|
sawine@7
|
10 |
\usepackage{multirow}
|
sawine@7
|
11 |
\usepackage[all]{xy}
|
sawine@7
|
12 |
\addtolength{\voffset}{-20pt}
|
sawine@7
|
13 |
\title{Spieltheorie \"Ubung 3}
|
sawine@7
|
14 |
\author{Eugen Sawin}
|
sawine@7
|
15 |
\renewcommand{\familydefault}{\sfdefault}
|
sawine@7
|
16 |
\newcommand{\E}{\mathcal{E}}
|
sawine@7
|
17 |
\newcommand{\R}{\mathcal{R}}
|
sawine@7
|
18 |
|
sawine@7
|
19 |
%\include{pythonlisting}
|
sawine@7
|
20 |
|
sawine@7
|
21 |
\pagestyle{empty}
|
sawine@7
|
22 |
\begin{document}
|
sawine@7
|
23 |
\maketitle
|
sawine@7
|
24 |
%
|
sawine@7
|
25 |
\section*{Aufgabe 3.1}
|
sawine@7
|
26 |
F\"ur alle Beispiele soll $n=1$ gelten.
|
sawine@7
|
27 |
\begin{description}
|
sawine@7
|
28 |
\item[$\mathbf{A}$ leer:] Sei $A=\emptyset$.\\
|
sawine@7
|
29 |
Mit $2^A=\{\emptyset\}$ folgt, dass f\"ur eine beliebige Funktion $f:A\to 2^A$, f\"ur jedes $x\in A$, $f(x) = \emptyset$ gilt. Somit hat $f$ keinen Fixpunkt, da es kein $x\in A$ mit $x\in f(x)$ gibt.
|
sawine@7
|
30 |
|
sawine@7
|
31 |
Aus der Verletzung der Bedingung, dass $A$ nicht leer sein darf, folgt somit auch die Verletzung der Bedingung, dass kein $f(x)$ leer sein darf.
|
sawine@7
|
32 |
\item[$\mathbf{A}$ nichtkonvex:] Sei $A=\{0,1\}$, also nicht-leer, kompakt aber nichtkonvex. Sei $f:A\to 2^A$ definiert durch $f(x)=\{1-x\}$.\\
|
sawine@7
|
33 |
Mit $f(0)=\{1\}$ und $f(1)=\{0\}$ gibt es kein $x\in A$ mit $x\in f(x)$, somit hat $f$ keinen Fixpunkt.
|
sawine@7
|
34 |
|
sawine@7
|
35 |
Ist $A$ konvex, z.B. $A=[0,1]$, also $A=\{x\mid x\in\mathbb{R},0\leq x\leq1\}$, so gibt es f\"ur die gleiche Funktion $f$ einen Fixpunkt mit $f(\frac{1}{2})=\{\frac{1}{2}\}$.
|
sawine@7
|
36 |
\item[$\mathbf{f}$ nicht ober-hemi-stetig:] Sei $A=[0,1]$ und $f(x)=\{\lceil 1-x \rceil\}$.\\
|
sawine@7
|
37 |
Da $Graph(f)=\{(1,0)\}\cup\{(x,1)\mid x\in[0,1)\}$ keine abgeschlossene Menge bildet, ist $f$ nicht ober-hemi-stetig. Mit $f(1)=\{0\}$ und $f(x)=\{1\}$ f\"ur alle $x\in A,x<1$, gibt es kein $x\in A$ mit $x\in f(x)$, somit hat $f$ keinen Fixpunkt.
|
sawine@7
|
38 |
\end{description}
|
sawine@7
|
39 |
|
sawine@7
|
40 |
\section*{Aufgabe 3.2}
|
sawine@7
|
41 |
Nach der Definition des erwarteten Nutzens gilt
|
sawine@7
|
42 |
\begin{align*}
|
sawine@7
|
43 |
U_i(\alpha_i',\alpha_{-i})=\sum_{b\in A}\left(\prod_{j\in N\setminus\{i\}}\alpha_j(b_j)\right) \alpha_i'(b_i) u_i(b)
|
sawine@7
|
44 |
\end{align*}
|
sawine@7
|
45 |
Wir unterscheiden jetzt die F\"alle $b_i = a_i$, $b_i = a_i'$ und die Aktionen mit unver\"anderter Verteilung. Daf\"ur sei $B=\{(a_i,b_{-i}) \mid b\in A\}$ die Menge aller Aktionsprofile mit Aktion $a_i$ f\"ur Spieler $i$ und $C=\{(a'_i,b_{-i}) \mid b\in A\}$ die Menge aller Aktionsprofile mit Aktion $a_i'$ f\"ur Spieler $i$. Um die Formel kompakt zu halten definieren wir zudem $\alpha'=(\alpha_i',\alpha_{-i})$.
|
sawine@7
|
46 |
\begin{align*}
|
sawine@7
|
47 |
U_i(\alpha')=\sum_{b\in A\setminus{B\cup C}}\left(\prod_{j\in N}\alpha_j'(b_j)\right)u_i(b)+\sum_{b\in B}\left(\prod_{j\in N}\alpha_j'(b_j)\right)u_i(b)+\sum_{b\in C}\left(\prod_{j\in N}\alpha_j'(b_j)\right)u_i(b)
|
sawine@7
|
48 |
\end{align*}
|
sawine@7
|
49 |
Wegen $\alpha_i'(a_i)=0$ und $\alpha_i'(b_i) = \alpha_i(b_i)$ f\"ur alle $i\in N$ und $b\in A\setminus B\cup C$ folgt
|
sawine@7
|
50 |
\begin{align*}
|
sawine@7
|
51 |
U_i(\alpha')&=\sum_{b\in A\setminus{B\cup C}}\left(\prod_{j\in N}\alpha_j(b_j)\right)u_i(b)+\sum_{b\in C}\left(\prod_{j\in N}\alpha_j'(b_j)\right)u_i(b)\\
|
sawine@9
|
52 |
U_i(\alpha')&=U_i(\alpha)-\sum_{b\in B}\left(\prod_{j\in N}\alpha_j(b_j)\right)u_i(b)-\sum_{b\in C}\left(\prod_{j\in N}\alpha_j(b_j)\right)u_i(b)+\sum_{b\in C}\left(\prod_{j\in N}\alpha_j'(b_j)\right)u_i(b)
|
sawine@7
|
53 |
\end{align*}
|
sawine@9
|
54 |
Wegen $B_i(a_{-i})=\{a_i\in A_i \mid u_i(a_{-1},a_i)\geq u_i(a_{-i},a_i')\text{ f\"ur alle } a_i'\in A_i\}$, $a_i'\in B_i(\alpha_{-i})$ und $a_i\notin B_i(\alpha_{-i})$ folgt, dass f\"ur alle $b \in B$ und $b'\in C$ gilt $u_i(b') > u_i(b)$. Zudem wurden bei der Verteilung $\alpha'$ die Wahrscheinlichkeiten aller $b'\in C$ mit den von $b\in B$ aufgestockt, d.h. f\"ur alle $b\in B$ und $b'\in C$ gilt
|
sawine@9
|
55 |
\begin{align*}
|
sawine@9
|
56 |
\alpha_i'(b')\cdot u_i(b')&=(\alpha_i(b')+\alpha_i(b))\cdot u_i(b')\\
|
sawine@9
|
57 |
\alpha_i'(b')\cdot u_i(b')&=\alpha_i(b')\cdot u_i(b')+\alpha_i(b)\cdot u_i(b')\\
|
sawine@9
|
58 |
\implies \alpha_i'(b')\cdot u_i(b')&> \alpha_i(b')\cdot u_i(b')+\alpha_i(b)\cdot u_i(b)
|
sawine@9
|
59 |
\end{align*}
|
sawine@9
|
60 |
Somit folgt
|
sawine@7
|
61 |
\[\sum_{b\in C}\left(\prod_{j\in N}\alpha_j'(b_j)\right)u_i(b)>\sum_{b\in B}\left(\prod_{j\in N}\alpha_j(b_j)\right)u_i(b)+\sum_{b\in C}\left(\prod_{j\in N}\alpha_j(b_j)\right)u_i(b)\]
|
sawine@7
|
62 |
\[\implies U_i(\alpha') > U_i(\alpha)\]\qed
|
sawine@8
|
63 |
|
sawine@8
|
64 |
\section*{Aufgabe 3.3}
|
sawine@8
|
65 |
Nach dem Support-Lemma, k\"onnen wir Strategie $X$ f\"ur Spieler 2 ausschlie{\ss}en, da bei einem NG $\alpha^*$ f\"ur jede reine Strategie $a_i\in supp(\alpha_i^*)$ gelten muss $a_i\in B_i(\alpha_{-i}^*)$ mit $B_i(\alpha_{-i}^*)=\{a_i\in A_i \mid U_i(\alpha_{-1}^*,a_i)\geq U_i(\alpha_{-i}^*,a_i')\text{ f\"ur alle } a_i'\in A_i\}$, d.h. $a_i$ ist eine beste Antwort auf $\alpha_{-i}^*$. Nur $B$ und $S$ werden dieser Bedingung f\"ur Spieler 2 gerecht.
|
sawine@8
|
66 |
|
sawine@8
|
67 |
Mit Hilfe des Lemmas ermitteln wir nun die Wahrscheinlichkeitsverteilungen.
|
sawine@8
|
68 |
\begin{align*}
|
sawine@8
|
69 |
U_1(B,\alpha_2^*)&=4\cdot\alpha_2^*(B)\\
|
sawine@8
|
70 |
U_1(S,\alpha_2^*)&=2\cdot\alpha_2^*(S)
|
sawine@8
|
71 |
\end{align*}
|
sawine@8
|
72 |
Wir wissen, dass f\"ur ein NG $U_1(B,\alpha_2^*)=U_1(S,\alpha_2^*)$ gelten muss. Au{\ss}erdem gilt $\alpha_2^*(B)+\alpha_2^*(S)=1$. Wir stellen die erste Gleichung entsprechend um und setzen das Ergebnis mit der zweiten Gleichung gleich und l\"osen auf.
|
sawine@8
|
73 |
\begin{align*}
|
sawine@8
|
74 |
4\cdot(1-\alpha_2^*(S))&=2\cdot\alpha_2^*(S)\\
|
sawine@8
|
75 |
4-4\cdot\alpha_2^*(S)&=2\cdot\alpha_2^*(S)\\
|
sawine@8
|
76 |
-6\cdot\alpha_2^*(S)&=-4\\
|
sawine@8
|
77 |
\alpha_2^*(S)&=\frac{2}{3} \implies \alpha_2^*(B)=\frac{1}{3}\\
|
sawine@8
|
78 |
\end{align*}
|
sawine@8
|
79 |
Wir k\"onnten $\alpha_1$ auf gleiche Weise herleiten, jedoch ist dies durch die Symmetrie der Nutzenfunktion nicht notwendig. Trivialerweise folgt $\alpha_1^*(B)=\frac{2}{3}$ und $\alpha_1^*(S)=\frac{1}{3}$.
|
sawine@8
|
80 |
|
sawine@8
|
81 |
Somit haben wir das NG ermittelt, es hat folgende Auszahlungen: $U_1(\alpha^*)=\alpha_1^*(B)\cdot\alpha_2^*(B)\cdot u_1(B,B)+\alpha_1^*(S)\cdot\alpha_2^*(S)\cdot u_1(S,S)=\frac{4}{3}=U_2(\alpha^*)$.
|
sawine@8
|
82 |
|
sawine@7
|
83 |
\end{document}
|