1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/exercises/solutions/sol05.tex	Sat Jun 09 22:15:16 2012 +0200
     1.3 @@ -0,0 +1,64 @@
     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 +\usepackage{tikz}
    1.16 +\usepackage{tikz-qtree}
    1.17 +\usetikzlibrary{decorations.pathmorphing} % noisy shapes
    1.18 +\usetikzlibrary{fit}					% fitting shapes to coordinates
    1.19 +\usetikzlibrary{backgrounds}	% drawin
    1.20 +\usetikzlibrary{shapes,snakes}
    1.21 +\addtolength{\voffset}{-20pt}
    1.22 +\title{Spieltheorie \"Ubung 5}
    1.23 +\author{Eugen Sawin}
    1.24 +\renewcommand{\familydefault}{\sfdefault}
    1.25 +\newcommand{\E}{\mathcal{E}}
    1.26 +\newcommand{\R}{\mathcal{R}}
    1.27 +
    1.28 +%\include{pythonlisting}
    1.29 +
    1.30 +\pagestyle{empty}
    1.31 +\begin{document}
    1.32 +\maketitle
    1.33 +%
    1.34 +\section*{Aufgabe 5.1}
    1.35 +(a) Wir zeigen, dass $u_i(O(s^*)) = u_i(O(r^*))$ f\"ur alle $i \in N$ gilt durch einen Widerspruchsbeweis.
    1.36 +
    1.37 +Wir nehmen an, dass $s^*\neq r^*$ (nicht-trivialer Fall) und $\exists{i\in N}: u_i(O(s^*)) > u_i(O(r^*))$.
    1.38 +
    1.39 +Da $\sum_{i\in N}u_i(O(s^*)) = 0$ gilt, folgt auch $\exists{j\in N}: u_j(O(s^*)) < u_j(O(r^*))$. Da $s^*$ ein TPG ist, gilt f\"ur alle Spieler $i$ und jede nicht-terminale Historie $h\in H\setminus Z$: $u_i|_h(O_h(s^*_{-i}|_h,s^*_i|_h))\geq u_i|_h(O_h(s^*_{-i}|_h,s_i))$.\\\\
    1.40 +(b) Wir geben ein Gegenbeispiel. Sei $\Gamma =\langle\{1,2\},\{\langle\rangle,\langle a\rangle,\langle b\rangle,\langle a,c\rangle,\langle a,d\rangle,\langle b,c\rangle,\langle b,d\rangle\}, P,(u_i)\rangle$ mit\\ $P(h)=1$ f\"ur $h=\langle\rangle$ und $P(h)=2$ sonst, $u_1(\langle a,d\rangle)=1$ und sonst $u_i(z)=0$ f\"ur alle Spieler $i$ und terminale Historien $z$.
    1.41 +
    1.42 +Wir sehen, dass u.a. $s^*=(a,dc)$ mit Auszahlung $u_1(O(s^*))=1$, und $r^*=(a,cc)$ mit Auszahlung $u_1(O(r^*))=0$ TPGs sind. \qed
    1.43 +
    1.44 +\section*{Aufgabe 5.2}
    1.45 +(b) Da wir in 5.1b bereits gezeigt haben, dass es im gleichen Spiel zwei TPGs geben kann mit unterschiedlichen Auszahlungen f\"ur einen oder mehr Spieler, gilt dies trivialerweise auch f\"ur zwei Spiele.
    1.46 +
    1.47 +Wir geben trotzdem ein Gegenbeispiel. Sei $G=\langle\{1,2\},(\{a,b\},\{c,d\}),(u_i)_{i\in\{1,2\}}\rangle$ mit $u_1(a,c)=1$ und sonst $u_i(a_1,a_2)=0$ f\"ur alle $i\in\{1,2\}$, $a_1\in\{a,b\}$ und $a_2\in\{c,d\}$.
    1.48 +
    1.49 +Strategie $s^*=(a,cc)$ ist ein TPG in $\Gamma_1$ mit Auszahlung $u_1(O(s^*))=1$ und Strategie $r^*=(d,aa)$ ein TPG in $\Gamma_2$ mit Auszahlung $u_1(O(r^*))=0$. \qed
    1.50 +
    1.51 +\section*{Aufgabe 5.3}
    1.52 +Wir rollen das Spiel vom Ende auf. Angenommen es seien nur noch Pirat 1 und Pirat 2 \"ubrig. Da Pirat 2 sonst sterben muss, wird er f\"ur die Aufteilung des Schatzes stimmen und mit 50\% der Stimmen wird dies auch geschehen, d.h. beide bekommen eine Auszahlung von $\frac{1}{2}$, alle anderen den Tod, sagen wir das sei $0$.
    1.53 +
    1.54 +Einen Schritt davor wissen die Piraten 1 und 2 \"uber den Ausgang ohne den Piraten 3. Da dieser besser ist, als den Schatz jetzt aufzuteilen, was eine Auszahlung von $\frac{1}{3}$ f\"ur jeden bedeutet, stimmen die Piraten 1 und 2 gegen die Aufteilung und \"uberstimmen somit Piraten 3, der get\"otet wird. Die Piraten 1 und 2 werden in allen vorherigen Schritten auch nicht von ihrer Strategie gegen die Aufteilung zu stimmen abweichen, da dies zum besten Resultat f\"ur beide f\"uhrt.
    1.55 +
    1.56 +Einen weiteren Schritt davor kenn Pirat 3 sein Schicksal im folgenden Schritt und wird zusammen mit Pirat 4, der um sein Leben k\"ampft, f\"ur die Aufteilung stimmen. Da beide zusammen 50\% der Stimmen haben, wird dies auch geschehen, d.h. die Piraten 1 bis 4 bekommen eine Auszahlung von $\frac{1}{4}$, alle anderen $0$. 
    1.57 +
    1.58 +Noch einen weiteren Schritt davor kennen Piraten 1 bis 4 den f\"ur sie positiven Ausgang im folgenden Schritt und werden somit mit ihrer Mehrheit gegen die Aufteilung stimmen. Pirat 5 wird get\"otet.
    1.59 +
    1.60 +Im vorherigen Schritt kennt Pirat 5 nun sein Schicksal und wird versuchen es mit seiner Stimme f\"ur die Aufteilung zu verhindern, was ihm gegen die Mehrheit von Piraten 1 bis 4 nicht gelingt.
    1.61 +
    1.62 +Erst in dem Schritt, in dem die zum Tode geweihten Piraten wieder 50\% der Stimmen erlangen, gelingt es ihnen ihren Tod zu verhindern und eine Auszahlung zu erzwingen. Dies geschieht immmer erst bei der doppelten Anzahl an Piraten.
    1.63 +
    1.64 +Daraus folgt, dass bei 8 Piraten eine Auszahlung f\"ur Piraten 1 bis 8 von $\frac{1}{8}$ und f\"ur die anderen $0$ gilt. Wir leiten die allgemeine Regel ab, f\"ur $n$ Piraten werden Piraten $n-2^{\lfloor\log(n)\rfloor}$ bis $n$ get\"otet und Piraten 1 bis $2^{\lfloor\log(n)\rfloor}$ bekommen eine Auszahlung von $\frac{1}{2^{\lfloor\log(n)\rfloor}}$.
    1.65 +
    1.66 +F\"ur $n=1000$ folgt daraus, dass Piraten 488 bis 1000 get\"otet werden und Piraten 1 bis 512 eine Auszahlung von $\frac{1}{512}$ bekommen.
    1.67 +\end{document}