sawine@14
|
1 |
\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
|
sawine@14
|
2 |
\usepackage{graphicx}
|
sawine@14
|
3 |
%\usepackage[latin1]{inputenc}
|
sawine@14
|
4 |
\usepackage{amsmath, amsthm, amssymb}
|
sawine@14
|
5 |
\usepackage{typearea}
|
sawine@14
|
6 |
\usepackage{algorithm}
|
sawine@14
|
7 |
\usepackage{algorithmic}
|
sawine@14
|
8 |
\usepackage{fullpage}
|
sawine@14
|
9 |
\usepackage{mathtools}
|
sawine@14
|
10 |
\usepackage{multirow}
|
sawine@14
|
11 |
\usepackage[all]{xy}
|
sawine@14
|
12 |
\usepackage{tikz}
|
sawine@14
|
13 |
\usepackage{tikz-qtree}
|
sawine@14
|
14 |
\usetikzlibrary{decorations.pathmorphing} % noisy shapes
|
sawine@14
|
15 |
\usetikzlibrary{fit} % fitting shapes to coordinates
|
sawine@14
|
16 |
\usetikzlibrary{backgrounds} % drawin
|
sawine@14
|
17 |
\usetikzlibrary{shapes,snakes}
|
sawine@14
|
18 |
\addtolength{\voffset}{-20pt}
|
sawine@14
|
19 |
\title{Spieltheorie \"Ubung 5}
|
sawine@14
|
20 |
\author{Eugen Sawin}
|
sawine@14
|
21 |
\renewcommand{\familydefault}{\sfdefault}
|
sawine@14
|
22 |
\newcommand{\E}{\mathcal{E}}
|
sawine@14
|
23 |
\newcommand{\R}{\mathcal{R}}
|
sawine@14
|
24 |
|
sawine@14
|
25 |
%\include{pythonlisting}
|
sawine@14
|
26 |
|
sawine@14
|
27 |
\pagestyle{empty}
|
sawine@14
|
28 |
\begin{document}
|
sawine@14
|
29 |
\maketitle
|
sawine@14
|
30 |
%
|
sawine@14
|
31 |
\section*{Aufgabe 5.1}
|
sawine@14
|
32 |
(a) Wir zeigen, dass $u_i(O(s^*)) = u_i(O(r^*))$ f\"ur alle $i \in N$ gilt durch einen Widerspruchsbeweis.
|
sawine@14
|
33 |
|
sawine@14
|
34 |
Wir nehmen an, dass $s^*\neq r^*$ (nicht-trivialer Fall) und $\exists{i\in N}: u_i(O(s^*)) > u_i(O(r^*))$.
|
sawine@14
|
35 |
|
sawine@14
|
36 |
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))$.\\\\
|
sawine@14
|
37 |
(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$.
|
sawine@14
|
38 |
|
sawine@14
|
39 |
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
|
sawine@14
|
40 |
|
sawine@14
|
41 |
\section*{Aufgabe 5.2}
|
sawine@14
|
42 |
(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.
|
sawine@14
|
43 |
|
sawine@14
|
44 |
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\}$.
|
sawine@14
|
45 |
|
sawine@14
|
46 |
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
|
sawine@14
|
47 |
|
sawine@14
|
48 |
\section*{Aufgabe 5.3}
|
sawine@14
|
49 |
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$.
|
sawine@14
|
50 |
|
sawine@14
|
51 |
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.
|
sawine@14
|
52 |
|
sawine@14
|
53 |
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$.
|
sawine@14
|
54 |
|
sawine@14
|
55 |
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.
|
sawine@14
|
56 |
|
sawine@14
|
57 |
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.
|
sawine@14
|
58 |
|
sawine@14
|
59 |
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.
|
sawine@14
|
60 |
|
sawine@14
|
61 |
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}}$.
|
sawine@14
|
62 |
|
sawine@14
|
63 |
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.
|
sawine@14
|
64 |
\end{document}
|