# Clustered and Rewritten Text Document This document groups text chunks based on semantic similarity. Topics and rewritten text (formatted in Markdown with LaTeX for equations) are generated by the Gemini API. ## Game Theory Basics Nash Equilibrium Dominant Strategies Prisoner's Dilemma Zero-Sum Games Conservative Strategies Mixed Strategies Checkpoints Summary Group Decisions Collective Choice # Spieltheorie: Eine Zusammenfassung Nicht-kooperative Spiele sind in der Literatur und in Anwendungen weit verbreitet. Spieler können keine Absprachen vor dem Spiel treffen und haben keinerlei Vereinbarungen über gemeinsame Aktionen, die optimal für die Gruppe sind. Eine zweite Unterscheidung betrifft simultane Spiele, bei denen alle Spieler ihre Wahl ein für alle Mal treffen (nur ein Zug). Spielen in reinen Strategien: Eine dominante Strategie $a_i$ ist mindestens so gut wie eine andere Strategie $a_i'$ für alle möglichen Aktionen der anderen Spieler $a_j \in A_j \neq i$, d.h. für alle $a_j \in A_j \neq i$ gilt $u_i(a_i, a_{-i}) \ge u_i(a_i', a_{-i})$. Gilt die Ungleichung im strengen Sinn ($>$), spricht man von starker Dominanz. Ein Nash-Gleichgewicht liegt vor, wenn kein Spieler durch eine einseitige Abweichung davon eine höhere Auszahlung erzielen kann. Das bedeutet, für alle $a_i \in A_i$ und $i \in N$ gilt: $u_i(a_i^*, a_{-i}^*) \ge u_i(a_i, a_{-i}^*)$. Was bedeutet das für das Gefangenendilemma…? Weiteres Beispiel: Falke-und-Taube-Spiel. Zwei Wettkämpfer müssen sich zwischen aggressivem (Falke) und nicht-aggressivem (Taube) Verhalten entscheiden. Die dominante Strategie beider Spieler ist G. ABER: Gleichgewicht (G, G) ist ineffizient, da (L, L) eine bessere Auszahlung ergeben würde. $$ \begin{array}{c|cc} & G & L \\ \hline G & (6, 6) & (8, 0) \\ L & (0, 8) & (3, 3) \\ \end{array} $$ Zwei-Personen-Nullsummenspiele: Spieler versuchen, den Gewinn zu maximieren (d.h. den Gewinn des anderen zu minimieren); der Verlust des einen ist der Gewinn des anderen (d.h. die Summe ist immer Null). Die Darstellung von 2PNS-Spielen erfolgt üblicherweise in Normalform (oder Matrixform). $$ \begin{array}{c|cc} & S_{21} & S_{22} \\ \hline S_{11} & (-1, 1) & (-5, 5) \\ S_{12} & (1, -1) & (3, -3) \\ \end{array} $$ Konservative Strategien: Die beste gegnerische Strategie führt zum eigenen schlechtesten Gewinn. Eine konservative Strategie wählt den besten Wert aus allen ungünstigsten Fällen. Der Minimierer P1 sucht $\max_i \min_j u_{1ij}$, der Maximierer P2 sucht $\min_j \max_i u_{1ij}$ (Schnittpunkt von Minimum und Maximum). Die Idee bleibt gleich: Keine Spielerin kann sich durch einen einseitigen Strategiewechsel verbessern. Beispiel: Schlacht in der Bismarcksee. Falls die Amerikaner die richtige Route überprüfen, kann die Bombardierung sofort begonnen werden (andernfalls verbleiben zwei Tage für die andere Route). Auf der Nordroute muss wegen schlechter Sicht die Bombardierung zudem einen Tag ausbleiben. Damit ergibt sich folgendes 2PNS-Spiel (Gewinn ≡ mögliche Tage für Bombardierung): $$ \begin{array}{c|cc} & N & S \\ \hline N & (2, -2) & (1, -1) \\ S & (0, 0) & (2, -2) \\ \end{array} $$ $\implies i^* = N$ und $U^- = 2 \implies j^* = N$ und $U^+ = 2 \implies$ Sattelpunkt bei (N, N). Spielen in gemischten Strategien: Reine Strategien legen *a priori* eine Strategie fest. Nachteil: Vorhersehbarkeit durch Mitspieler. Im Fall eines Sattelpunkts wird das 2PNS-Spiel mit Wahrscheinlichkeiten $p$ und $q$ multipliziert. Die Lösung der zugehörigen Gleichung erfolgt oft durch lineare Programmierung. $$ \begin{array}{c|cc} & S_{21} & S_{22} \\ \hline S_{11} & 1 & -5 \\ S_{12} & 3 & -1 \\ \end{array} $$ $\implies$ Sattelpunkt der Funktion (graphisch) bei $p = 0.5$ und $q = 0.25$. Checkpoints: Spiele in reinen Strategien, Darstellung in Normalform/Bimatrixform, dominante Strategie, Nash-Gleichgewicht, Zwei-Personen-Nullsummenspiele. Gruppenentscheidungen: Gesucht ist eine kollektive Auswahlfunktion $K$ für die Präferenz der Gesamtheit: $K: PA = PA \times PA \times \dots \times PA \to PA$. Wesentliche Bedingungen: Die Auswahlfunktion $K$ muss total sein. Für jede mögliche Kombination von (persönlichen) Präferenzen aus $PA$ muss es eine Gesamtpräferenz (also ein Ergebnis) geben. Das Ergebnis selbst muss wieder eine Relation in $PA$ sein. Entscheidungsverfahren (Fortsetzung): Rangaddition. Jede Individualpräferenz $\rho_i$ legt eine Rangabbildung fest. Die kollektive Präferenz wird aus den Rangnummern der jeweiligen Individuen bestimmt. Einfache Methode: Addition der Rangnummern. Für zwei Elemente x, y gilt: $K_A(\rho_1, \dots, \rho_n)$ ist Relation $\rho$ mit $\sum r_i$. Die Summe $\sum r_i$ ist keine Rangabbildung, kann aber leicht korrigiert werden, sodass $\rho \in PA$ gilt. Das Verfahren hat keine offensichtlichen Nachteile. Kollektive Auswahlfunktionen $PA \to PA$ werden auch von unerwünschten Verfahren erfüllt. Zwei Bedingungen, die jedes „gerechte“ Verfahren erfüllen sollte: Pareto-Bedingung: Die Gesamtheit kann für beliebige Wahlmöglichkeiten durch Einstimmigkeit jede gewünschte Rangfolge erzwingen. Unabhängigkeit von irrelevanten Alternativen: Die Rangfolge zwischen zwei Wahlmöglichkeiten wird nur von den Präferenzen bezüglich dieser beiden Möglichkeiten bestimmt. --- ## Game Theory Basics Two-Person Zero-Sum Games Bismarck Sea Battle Mixed Strategies Game Group Decisions Preferences & Relations Decision Procedures Arrow's Impossibility Theorem # Spieltheorie: Eine Einführung Zwei-Personen-Nullsummenspiele (2PNS-Spiele) werden auch als MinMax-Spiele bezeichnet. In Matrixform wird Spieler 1 zur Minimiererin (Zeilenspielerin) und Spieler 2 zur Maximiererin (Spaltenspielerin). Aufgrund der speziellen Struktur von 2PNS-Spielen nehmen Nash-Gleichgewichte die Form von Sattelpunkten an (Schnittpunkt von Minimum und Maximum). Der Min-Max-Theorem besagt: Ein Sattelpunkt existiert genau dann, wenn $U^- = a_{i^*j^*} = U^+$. Ein Beispiel hierfür ist die Schlacht in der Bismarcksee (2.-4. März 1943): Japanische Truppen sollen von Rabaul nach Lae verlegt werden, wobei zwei Routen zur Verfügung stehen: eine regnerische Nordroute und eine sonnige Südroute. Der japanische Konvoi ist unabhängig von der gewählten Route drei Tage unterwegs. Die U.S. Air Force möchte den Konvoi bombardieren, hat aber nicht genügend Flugzeuge, um beide Routen gleichzeitig zu überwachen. Die Amerikaner müssen eine Entscheidung treffen. Möglichkeiten: Aktionen: $A_1 = \{X, Y\}$ und $A_2 = \{X, Y\}$. Aktionsprofile: $A = \{(X, X), (X, Y), (Y, X), (Y, Y)\}$. Auszahlungsfunktion: $u_{1,2}: A \to (1, 0, 0, 1)$. Wie verändert sich das Spiel, wenn folgende Auszahlungsfunktionen gelten? Spieler 1: $u_1: A \to (1, 0, 0, 0)$; Spieler 2: $u_2: A \to (0, 0, 0, 1)$. Spielen in gemischten Strategien: Aufgabe: Steuerhinterziehung. Wie ändert sich die Situation für den Fall $s > 200$ Mio. CHF? Problem: Keine dominante Strategie / kein Nash-Gleichgewicht in reinen Strategien. Wenn $q$ in $S_{22}$ sowie $p$ in $S_{11}$ oder $S_{12}$ gilt, ergibt sich $U^- = 2 = U^+$. Gruppenentscheidungen: Relationen beschreiben Beziehungen (z.B. Rangfolgen, Präferenzen) zwischen Elementen. Darstellung als Relation $R$ auf Paaren $(x, y)$ von Elementen aus $A$, formal geschrieben als $(x, y) \in R$ oder abkürzend als $xRy$. Beispiel: Mit $R$ ist ‘$<$’ (kleiner) und $xRy$ folgt $x < y$. Eigenschaften von Relationen... Präferenzen: Rangabbildungen definieren eine Präferenzrelation: $x \rho y \iff r(x) < r(y)$. Relation $\rho$ ist transitiv und asymmetrisch. Die Menge aller (möglichen) darstellbaren Relationen auf $A$ ist definiert als $P_A := \{\rho \subset A \times A: \rho \text{ erfüllt } x \rho y \iff r(x) < r(y) \text{ für eine Rangabbildung } r\}$. Erweiterung der Relation durch alle Paare mit gleichem Rang: $x \rho^* y \iff r(x) \le r(y)$. Relation $\rho^*$ ist transitiv und reflexiv. Es gilt offensichtlich $\rho \subset \rho^*$. Analog zur Menge $P_A$ lässt sich damit definieren $P_A^* := \{\rho^* \subset A \times A: \rho^* \text{ erfüllt } x \rho^* y \iff r(x) \le r(y) \text{ für eine Rangabbildung } r\}$. Beispiel: $A = \{x, y, z\}$, $r(x) = 1$, $r(y) = r(z) = 2$. Zwischen beiden Relationen gilt folgende Beziehung: $x \rho y \iff \neg(y \rho^* x)$. Rangabbildungen vor allem für... Entscheidungsverfahren: Extrembeispiel 1: Externer Diktator. Für beliebiges $\rho_E \in P_A$ gilt... Ergebnis ist offensichtlich Abbildung $P_A \to P_A$, aber unabhängig von den $\rho_i$. Verfahren kann kaum als „gerecht“ oder „demokratisch“ bezeichnet werden. Extrembeispiel 2: Interner Diktator. Festlegung eines Individuums $d \in I$, dessen Präferenz $\rho_d$ das Ergebnis bestimmt. Damit gilt... Rangaddition: Beispiel: $I = \{1, 2\}$, $A = \{x, y, z\}$. Rangaddition hat keine offensichtlichen Nachteile, liefert aber ggf. unschöne Ergebnisse. Mehrheit: Es folgt $x \rho y$, $y \rho z$ und $z \rho x$. Aus der Transitivität folgt schließlich $x \rho x \to$ kein gültiges Ergebnis, d.h. $\rho \notin P_A$. Einstimmigkeit: Element $x$ wird Element $y$ vorgezogen $\iff$ alle Individuen teilen diese Präferenz für alle. ABER: Ein einziges Individuum, das $y$... Rangfolge zwischen zwei Wahlmöglichkeiten kann nicht durch Präferenzänderungen der Individuen im Hinblick auf eine dritte Wahlmöglichkeit gekippt werden. Problem: Bereits mit diesen zwei Forderungen kein annähernd demokratisches Verfahren mehr möglich (Satz von Arrow). Quintessenz: Demokratie funktioniert nicht…? Bedingungen an Auswahlverfahren: Möglichkeit $z$ soll keinen Einfluss auf Ergebnis haben. Oder formal: Wenn kein Individuum Präferenz $\rho_i, \rho_i' \in P_A$ bzgl. $x$ und $y$ ändert, soll gelten (für alle) $\implies$ (...). Rangaddition somit als „gerechtes“ Verfahren ausgeschlossen. Condorcet-Verfahren und Einstimmigkeit liefern für $|A| > 2$ evtl. ungültiges Ergebnis. Nur interner Diktator $K_D$ erfüllt alle Bedingungen. Der Diktator ist „großzügiger“ gegenüber anderen Gruppenmitgliedern. Bei Indifferenz (es gilt weder $x \rho_d y$ noch $y \rho_d x$) beliebige Rangfolgen von $x, y$ zulässig. US-Wahlen haben nur zwei Kandidaten. --- ## Game Theory Introduction # Einführung in die Spieltheorie (CDS-1012) HS 2024 Prof. Dr. rer. nat. habil. Ralf-Peter Mundani, DAViS **Einleitung:** Ein Überblick über die Spieltheorie, ein Teilgebiet der Mathematik, das das strategische Denken modelliert. Wir behandeln die Modellierung von Entscheidungssituationen, Spiele in reinen Strategien, das Nash-Gleichgewicht und dominante Strategien, Zwei-Personen-Nullsummenspiele, konservative Strategien, Spiele in gemischten Strategien und die Berechnung von Sattelpunkten. Mehrheitsbeschlüsse und Gruppenentscheidungen werden im zweiten Teil behandelt. **Motivation aus der Stochastik: Das Ziegenproblem (a.k.a. Monty-Hall-Dilemma):** Eine Spielshow mit drei Türen – zwei Ziegen und ein Auto. Der Spieler wählt eine Tür, der Showmaster öffnet eine andere Tür mit einer Ziege. Sollte der Spieler seine Wahl ändern? Die Fälle, in denen der Spieler Tür B oder C wählt, sind symmetrisch. In drei von neun Fällen verliert der Spieler, in sechs von neun Fällen gewinnt er. Das Ändern der Wahl ist also vorteilhaft. **Grundlagen:** Die Spieltheorie modelliert Entscheidungssituationen, in denen die Akteure (Spieler) ihre Wahl gleichzeitig und nur einmal treffen (ein Durchlauf). Eine übliche Darstellung ist die Normalform (z.B. Gefangenendilemma). Sequentielle Spiele weisen eine spezifische Ordnung auf, die bestimmt, welcher Spieler wann entscheidet. Spieler haben in jedem Schritt vollständiges oder unvollständiges Wissen über den aktuellen Status (frühere Entscheidungen). Die übliche Darstellungsform ist extensiv oder als Baum. **Spiele in reinen Strategien:** Das Gefangenendilemma ist ein bekanntes nicht-kooperatives Spiel in reinen Strategien. Zwei Gefangene werden beschuldigt, gemeinsam ein Verbrechen begangen zu haben. Sie werden getrennt vernommen und können nicht kommunizieren. Mangels Beweisen kann beiden nur ein Teil der Tat nachgewiesen werden. Mögliche Aktionen sind Leugnen (L) mit einer niedrigen Strafe (2 Jahre) und Gestehen (G) mit einer hohen Strafe (5 Jahre) oder Höchststrafe (8 Jahre – Kronzeugenregel). Die Auszahlung wird durch die Funktion $u_i$ modelliert, die den Gewinn an Freiheit (Höchststrafe – tatsächliche Strafe) darstellt. **Gefangenendilemma (Fortsetzung):** Die Darstellung in Normalform (bei zwei Spielern auch Bimatrixform genannt) lautet: | | G | L | | :---- | :---- | :---- | | **G** | (6, 6) | (8, 0) | | **L** | (0, 8) | (3, 3) | Die Frage ist: Wie finden beide Spieler die für sie beste Strategie? **Ein bisschen Mathematik:** Das Nash-Gleichgewicht ist ein Aktionsprofil, bei dem kein Spieler einen Anreiz hat, seine Strategie einseitig zu ändern. Eine stark dominante Strategie $a_i$ ist besser als jede andere Strategie $a_i$ unabhängig von den Strategien der anderen Spieler. Profile dominanter Strategien führen zu Nash-Gleichgewichten (die Umkehrung gilt nicht). Was bedeutet das für das Gefangenendilemma? **Stark dominante Strategie:** Die stark dominante Strategie beider Spieler ist G. **Übung: Steuerhinterziehung:** Ein Unternehmen, Zanoma, hat 200 Millionen CHF nicht versteuert. Wird die Steuerhinterziehung nachgewiesen, muss das Unternehmen eine Nachzahlung von $s$ Millionen CHF (Steuer plus Busse) leisten. Der Steuerprüfer erhält im Erfolgsfall 5% der Nachzahlung als Prämie. Der Steuerprüfer hat die Strategien Prüfung (P; Kosten: 10M CHF) und keine Prüfung (KP; Kosten: 0). Zanoma hat die Strategien Steuerhinterziehung (S) und keine Steuerhinterziehung (KS). a) Wie sieht die Situation als Spiel in Bimatrixform aus? b) Gibt es für $s < 200$M CHF dominante Strategien und Nash-Gleichgewichte? **(jede Ähnlichkeit mit real existierenden Unternehmen ist rein zufällig)** **Konservative Strategien:** Konservative Strategien minimieren den maximal möglichen Verlust (Minimax). Der Minimierer $P_1$: $U^- = \min_i \max_j a_{ij}$. Der Maximierer $P_2$: $U^+ = \max_j \min_i a_{ij}$. **Spiele in gemischten Strategien:** Spiele in gemischten Strategien haben immer einen Sattelpunkt. Spieler $P_1$ spielt mit Wahrscheinlichkeit $p$ Strategie $S_{11}$ und mit $1-p$ Strategie $S_{12}$. Spieler $P_2$ spielt mit Wahrscheinlichkeit $q$ Strategie $S_{21}$ und mit $1-q$ Strategie $S_{22}$. Für den Fall $n > 2$ Strategien werden Wahrscheinlichkeiten $p_1, p_2, \dots, p_n$ verwendet. **Steuerhinterziehung (Fortsetzung):** Aus Sicht von Zanoma: $(200 - s) \cdot q + 200 \cdot (1 - q) = 0 \cdot q + 0 \cdot (1 - q) \iff q = \frac{200}{s}$. Aus Sicht des Steuerprüfers: $(0.05 \cdot s - 10) \cdot p - 10 \cdot (1 - p) = 0 \cdot p + 0 \cdot (1 - p) \iff p = \frac{200}{s}$. Das Nash-Gleichgewicht in gemischten Strategien ist somit für $p = q$, d.h. für $(\frac{200}{s}, \frac{200}{s})$. Höhere Nachzahlungen (Bussen) senken die Wahrscheinlichkeit der Prüfung. **Gruppenentscheidungen:** Der Satz von Arrow: Sei $A$ mit $|A| > 2$ eine Menge von Auswahlmöglichkeiten. $K: PA \to PA$ sei eine kollektive Auswahlfunktion, die die Pareto-Bedingung und Unabhängigkeit von irrelevanten Alternativen erfüllt. Dann existiert immer ein Diktator $d \in I$: Für alle $(\rho_1, \dots, \rho_n) \in PA$: Für alle $(x, y) \in A \times A$: $x \rho_d y \implies x \rho y$. ABER: Der Diktator ist „großzügiger“ gegenüber anderen. --- ## Game Theory Basics Nicht-kooperative Spiele zeichnen sich dadurch aus, dass alle Spieler ihre Auszahlung maximieren, indem sie ihre beste Strategie wählen – basierend auf ihrem Wissen oder ihren Erwartungen bezüglich der Strategien der anderen Spieler. Vereinbarungen zwischen den SpielerInnen gibt es nicht. Im Gegensatz dazu stehen kooperative Spiele, bei denen alle SpielerInnen nach gemeinsamen Aktionen suchen, die optimal für die gesamte Gruppe sind. In kooperativen Spielen können die SpielerInnen vor Spielbeginn Absprachen treffen. --- ## Game Theory Strategies Mixed Strategies Group Decision Making Preference Rankings Decision Procedures # Gruppenentscheidungen und Entscheidungsverfahren Vorhersehbarkeit durch Mitspieler*innen ist ein wichtiges Thema. Ein Beispiel: Schere (100%), Stein (0%), Papier (0%) repräsentiert eine reine Strategie. Gemischte Strategien hingegen bedeuten, dass eine Spieler*in zufällig zwischen Strategien entscheidet. Formal lässt sich dies als Wahrscheinlichkeitsfunktion über (reinen) Strategien charakterisieren. Beispiel: Schere (25%), Stein (50%), Papier (25%). Reine Strategien führen aber häufig nicht zu Nash-Gleichgewichten. Nicht jedes Zwei-Personen-Nullsummenspiel (2PNS-Spiel) in reinen Strategien hat einen Sattelpunkt. Betrachten wir das Beispiel: $$ \begin{array}{c|cc} & S_{21} & S_{22} \\ \hline S_{11} & 3 & -1 \\ S_{12} & -1 & 5 \\ \end{array} $$ Hier gilt: $\min_i \max_j = 3$ und $\max_j \min_i = 1$. Daher ist $i^* = S_{11}$ und $j^* = S_{22}$, mit $U^- = 3$ und $U^+ = 1$. Zwei-Personen-Nullsummenspiele in gemischten Strategien haben immer einen Sattelpunkt. Dies wird durch das Min-Max-Theorem nochmals verdeutlicht. Situationen mit unerwünschten Ergebnissen sind in der Regel nicht vermeidbar, auch abhängig von den gewählten Entscheidungsverfahren. Rangabbildungen sind ein hilfreiches Werkzeug bei Gruppenentscheidungen. Gegeben ist eine endliche Menge $A$ von Möglichkeiten (z.B. Kandidat*innen, Pläne...). Präferenzen entstehen durch die Vergabe von Rangnummern $r(x)$ mit $x \in A$. Für zwei Möglichkeiten $x, y \in A$ bedeutet $r(x) < r(y)$, dass $x$ gegenüber $y$ bevorzugt wird. Zwei (oder mehr) Möglichkeiten können dieselbe Rangnummer erhalten. Eine Rangabbildung $r: A \to P$ ist eine surjektive Abbildung der Menge der Möglichkeiten $A$ auf eine Menge von Präferenzen $P = \{1, \dots, k\} \subset \mathbb{N}$. Beispiel: $A = \{x, y, z\}$, $P = \{1, 2\}$ $r(x) = 1$, $r(y) = r(z) = 2$. Surjektivität bedeutet, dass jedes Element der Bildmenge mindestens ein zugehöriges Element in der Urbildmenge hat. Eigenschaften von Relationen sind wichtig: Transitiv: Mit $xRy$ und $yRz$ folgt auch $xRz$ (z.B. aus $2 < 3$ und $3 < 4$ folgt $2 < 4$). Reflexiv: $xRx$ gilt für alle $x \in A$ (z.B. $2 \le 2$). Asymmetrisch: $xRy$ und $yRx$ gelten niemals gleichzeitig (z.B. $2 < 3$, aber nicht $3 < 2$). Transitive und reflexive Relationen werden auch Quasiordnungen genannt. Rangabbildungen eignen sich vor allem für Visualisierungen (z.B. Fussballtabellen). Betrachten wir nun Entscheidungsverfahren. Die Menge der Wähler*innen $I = \{1, \dots, n\}$ besteht aus Individuen, durchnummeriert von 1 bis n. Jede*r Wähler*in hat eine persönliche Präferenz $P_i$. Gesucht ist eine kollektive Auswahlfunktion. Mehrheitsentscheidung (Condorcet-Verfahren): Im direkten Vergleich zweier Elemente $x, y \in A$ gibt es Individuen $\{i \in I: x \rho_i y\}$, die $x$ bevorzugen, Individuen $\{i \in I: y \rho_i x\}$, die $y$ bevorzugen, und Individuen, die bezüglich $x$ und $y$ indifferent sind. Das Condorcet-Verfahren zählt, wer mehr Vergleiche gewinnt. Für zwei Elemente $x, y$ gilt: $K_C(\rho_1, \dots, \rho_n)$ ist eine Relation $\rho$. Das Verfahren ist für beliebige $\rho$ durchführbar, aber die Relation $\rho$ ist im Fall von mehr als zwei Möglichkeiten nicht immer transitiv, d.h. $\rho$ ist keine zulässige Präferenzrelation aus $P_A$. Beispiel: $I = \{1, 2, 3\}$, $A = \{x, y, z\}$. Es folgt $x \rho y$, $y \rho z$ und $z \rho x$. Aus der Transitivität würde $x \rho z$ folgen, was aber nicht der Fall ist. In der Praxis liefert das Verfahren keine echten Präferenzen (außerdem: für $|A| > 2$, $\rho \notin P_A$). Beispiel: $i = 1$: $x < y < z$ und $i = 2$: $y < z < x$. $\rho$ enthält genau ein Paar $y \rho z \implies \rho \notin P_A$. Bedingungen an Auswahlverfahren: Pareto-Bedingung (Einstimmigkeit): Eine kollektive Auswahlfunktion $K: P_A \to P_A$ erfüllt die Pareto-Bedingung, wenn für alle $\rho_i \in P_A$ gilt: für alle $x, y \in A$ mit $x \rho_i y$ für alle $i \in I$ folgt $x \rho y$. Somit scheidet der externe Diktator aus, alle anderen Verfahren erfüllen die Bedingung. Beispiel: Beide Individuen sehen $x, y$ vor $z$. Unabhängigkeit von irrelevanten Alternativen: Die Platzierung einer dritten Möglichkeit $z$ soll keinen Einfluss auf die Rangordnung zwischen $x$ und $y$ haben. Eine Präferenzänderung bei einem Individuum kann die kollektive Präferenz beeinflussen. --- ## Game Theory Basics # Spieltheorie: Grundlagen und Anwendungen Die Spieltheorie modelliert Entscheidungssituationen, oft in sozialen Konflikten. Der Erfolg hängt dabei nicht nur von den eigenen, sondern auch von den Entscheidungen anderer ab. Wichtige Anwendungsgebiete sind die Wirtschaftswissenschaften und Ökonomie. Bekannte Vertreter sind John von Neumann und John Forbes Nash. Man unterscheidet zwischen kooperativen und nicht-kooperativen Spielen sowie simultanen und sequentiellen Spielen. Grundlagen: Entscheidungen können unter Gewissheit (alle Aktionen und Konsequenzen sind bekannt), Risiko (bestimmte Wahrscheinlichkeiten von Aktionen und Konsequenzen sind bekannt) und Unsicherheit (keine Aktionen und Konsequenzen sind bekannt) getroffen werden. Die Modellierung umfasst: eine Menge von SpielerInnen $N = \{1, 2, \dots, n\}$, eine Menge der Aktionen (auch Strategien genannt) $A_i$ von SpielerIn $i$ für alle $i \in N$, und eine Menge der Aktionsprofile (auch Strategieprofile) $A = \{(a_i)_{i \in N}, a_i \in A_i \text{ für alle } i \in N\}$. Die Auszahlungsfunktion $u_i: A \to \mathbb{R}$ beschreibt die Auszahlung für SpielerIn $i$. Beispiel: Entscheidung zwischen zwei Möglichkeiten mit Aktionen $A_1 = \{X, Y\}$ und ... ... ein Nash-Gleichgewicht liegt vor, wenn keine SpielerIn durch einseitige Abweichung von ihrer Entscheidung (während alle anderen SpielerInnen bei ihren Entscheidungen bleiben) eine höhere Auszahlung erzielen kann. Formal: Ein Aktionsprofil bildet genau dann ein Nash-Gleichgewicht, wenn keine der SpielerInnen durch Abweichung davon eine höhere Auszahlung erhält. Zwei-Personen-Nullsummenspiele: Hier ist der Gewinn einer SpielerIn der Verlust der anderen (die Summe ist immer null). Die USA nutzten diese Spielart während der Kuba-Krise für strategische Analysen. Das Spiel wird interessant, wenn die Kosten für den Kampf ($C$) die Kosten bzw. den Wert des Sieges ($V$) überschreiten, d.h. $C > V > 0$. Übung: Steuerhinterziehung. Unternehmen Zanoma hat durch kreative Buchführung 200 Millionen CHF nicht versteuert. Falls $s < 200$, folgt $200 - s > 0$, also ist S eine strikt dominante Strategie. Falls $s < 200$, folgt $0.05 \cdot s - 10 < 0$, also ist KP eine strikt dominante Strategie. Spielen in gemischten Strategien: Alternative Berechnung (als reine Strategien) aus der jeweiligen Sicht von SpielerIn P1 und P2. Sattelpunkt bei (0.5, 0.25); durch Einsetzen von $p$ in $S_{21}$ oder $S_{22}$ sowie $q$ in $S_{11}$ oder $S_{12}$ ergibt sich ... $f(x,y) = -8xy + 2x + 4y + 1$ und `splot [0:1][0:1] f(x,y)`. Zwei-Personen-Nullsummenspiele: Darstellung in Matrixform. Konservative Strategien (MinimiererIn/MaximiererIn). Spiele in gemischten Strategien. Gleichgewichtspunkte/Sattelpunkt. Gruppenentscheidungen: Verschiedene Möglichkeiten (Entscheidungsvarianten: Wahlen, Wettbewerbe, ...). Ziel: Gemeinsame Bestimmung einer Rangfolge der Möglichkeiten. Beispiel: WählerInnen ➡️ KandidatInnen (Wahl), Publikum ➡️ TeilnehmerInnen (Wettbewerb). Nicht alle werden mit der Rangfolge einverstanden sein (Unzufriedenheit). Axiomatischer Ansatz: Aufstellung von Eigenschaften und Prüfung, welche Entscheidungsverfahren sie erfüllen. Modellierung individueller Präferenzen und der Entscheidungsverfahren selbst. Bedingungen an Auswahlverfahren: Unabhängigkeit von irrelevanten Alternativen. Beispiel: $I = \{1, 2\}$, $A = \{x, y, z\}$ mit Rangaddition $K_A$ als Auswahlverfahren. Als Gruppenentscheidung bzgl. $x$ und $y$ gilt $y \rho' x$, aber nicht $x \rho y$. Das Ergebnis ändert sich, obwohl kein Individuum die Präferenz im direkten Vergleich zwischen $x$ und $y$ ändert ($i=1$ sieht $x < y$ und $i=2$ ...).