1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/exercises/solutions/sol03.tex	Sat May 19 22:50:05 2012 +0200
     1.3 @@ -0,0 +1,57 @@
     1.4 +\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
     1.5 +\usepackage{graphicx}
     1.6 +%\usepackage[latin1]{inputenc}
     1.7 +\usepackage{amsmath, amsthm, amssymb}
     1.8 +\usepackage{typearea}
     1.9 +\usepackage{algorithm}
    1.10 +\usepackage{algorithmic}
    1.11 +\usepackage{fullpage}
    1.12 +\usepackage{mathtools}
    1.13 +\usepackage{multirow}
    1.14 +\usepackage[all]{xy}
    1.15 +\addtolength{\voffset}{-20pt}
    1.16 +\title{Spieltheorie \"Ubung 3}
    1.17 +\author{Eugen Sawin}
    1.18 +\renewcommand{\familydefault}{\sfdefault}
    1.19 +\newcommand{\E}{\mathcal{E}}
    1.20 +\newcommand{\R}{\mathcal{R}}
    1.21 +
    1.22 +%\include{pythonlisting}
    1.23 +
    1.24 +\pagestyle{empty}
    1.25 +\begin{document}
    1.26 +\maketitle
    1.27 +%
    1.28 +\section*{Aufgabe 3.1}
    1.29 +F\"ur alle Beispiele soll $n=1$ gelten.
    1.30 +\begin{description}
    1.31 +  \item[$\mathbf{A}$ leer:] Sei $A=\emptyset$.\\
    1.32 +  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.
    1.33 +
    1.34 +  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.
    1.35 +  \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\}$.\\
    1.36 +  Mit $f(0)=\{1\}$ und $f(1)=\{0\}$ gibt es kein $x\in A$ mit $x\in f(x)$, somit hat $f$ keinen Fixpunkt.
    1.37 +
    1.38 +  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}\}$.
    1.39 +  \item[$\mathbf{f}$ nicht ober-hemi-stetig:] Sei $A=[0,1]$ und $f(x)=\{\lceil 1-x \rceil\}$.\\
    1.40 +  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.
    1.41 +\end{description}
    1.42 +
    1.43 +\section*{Aufgabe 3.2}
    1.44 +Nach der Definition des erwarteten Nutzens gilt
    1.45 +\begin{align*}
    1.46 +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)
    1.47 +\end{align*}
    1.48 +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})$.
    1.49 +\begin{align*}
    1.50 +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)
    1.51 +\end{align*}
    1.52 +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
    1.53 +\begin{align*}
    1.54 +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)\\
    1.55 +&=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)
    1.56 +\end{align*}
    1.57 +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 $\alpha_i'(b')\cdot u_i(b') > \alpha_i(b)\cdot u_i(b)+\alpha_i(b')\cdot u_i(b')$. Somit folgt 
    1.58 +\[\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)\]
    1.59 +\[\implies U_i(\alpha') > U_i(\alpha)\]\qed
    1.60 +\end{document}