Lehre

Obgleich Nashgleichgewichte das wohl bekannteste Lösungskonzept der Spieltheorie darstellen, sind sie doch eher theoretischer Natur. Damit ist gemeint, dass sich Personen in tatsächlichen Spielsituationen gar nicht, oder nur selten nach dem Nachgleichgewicht richten. Um diese Diskrepanz zwischen mathematischer Vorhersage und tatsächlichem Spielverhalten zu überbrücken, führen wir Stellvertreterspiele als eine weitere Ebene in Normalformspielen ein. Die Hauptidee hierbei ist es, zwischen der Auszahlung die ein Spieler erhält, und seinem/ihrem tatsächlichen Nutzen zu unterscheiden. In dieser Masterarbeit, welche auf den Ergebnissen von Stefan Zeuner und dessen Masterarbeit aufbaut, konnten wir zeigen, dass N-Personen-Spiele mit reinem Nashgleichgewicht stets auch ein reines Stellvertretergleichgewicht haben. Dies stellt eine Verallgemeinerung von Zeuners Resultat über 2-Personen-Spiele dar. Ebenfalls wird eine vollständige Charakterisierung von 2x2-Normalformspielen angegeben und gezeigt, dass diese stets ein reines Stellvertretergleichgewicht besitzen (unter der Voraussetzung, dass die Auswahlfunktion Phi pareto-optimale Ausgänge bevorzugt). Ebenso konnte gezeigt werden, dass die Auszahlungsfunktion des Stellvertreterspiels niemals stetig sein kann, was unsere Möglichkeiten bestehende Resultate bezüglich der Existenz von Nashgleichgewichten zu nutzen, erheblich einschränkt; Und wir konnten zeigen, dass das Konzept von Vertreterspielen (unter gewissen Voraussetzungen) einige grundlegende Probleme mit sich bringt, welche dem Satz von Gibbard-Satterthwaite, sowie Arrows Unmöglichkeitstheorem zuzuschreiben sind. Trotz dieser beiden vorhergehenden Ergebnisse konnte ein reines Stellvertretergleichgewicht (mit Beweis) für ein Spiel angegeben werden, welches mit keiner der vorher bekannten Methoden behandelt werden konnte. Ein möglicher Grund warum diese Art Lösung funktioniert und wie man sie gegebenenfalls auch auf andere Spiele ausweiten kann, wird ebenfalls angedeutet.

Gegeben sei ein einfacher, endlicher, ungerichteter Graph G = (V,E) mit Eckenmenge V (G) und Kantenmenge E(G). Die Kreuzungszahl eines Graphen G, die mit cr(G) bezeichnet wird, ist das Minimum aller Kantenkreuzungen über alle Zeichnungen von G in der Ebene. Diese ist eine wichtige Messgröße für die Charakterisierung der Nichtplanarität eines Graphen. Aufgrund der schweren Berechenbarkeit des dazugehörigen Entscheidungsproblems ist es gerechtfertigt, sich mit Schranken zu beschäftigen. Diese Masterarbeit liefert einen Beweis für eine obere Schranke für Graphen, die mit beschränkter Verzerrung eingebettet werden können. Unabhängig davon wird ein neues Separator-Theorem angegeben, das ein konstantes Größenverhältnis bei den Komponenten eines Graphen G erzeugt, die durch den Trenner S entstehen. Trenner von Graphen sind mächtige Werkzeuge, die durch den Teile-und-herrsche-Algorithmus motiviert sind.

In der nicht kooperativen Spieltheorie existiert kein komplett zufriedenstellendes Lösungskonzept. Selbst das häufig verwendete Nash-Gleichgewicht liefert nicht immer plausible Ergebnisse, sodass in der aktuellen Forschung nach neuen besseren Lösungskonzepten gesucht wird. In dieser Arbeit wird ein neues Lösungsverfahren für 2-Personen Normalformspiele vorgestellt, welches iterativ vorgeht. Nach der Definition werden erste Eigenschaften gezeigt, bevor es auf verschiedene bekannte Beispiele der Spieltheorie angewendet wird. Anhand dieser Spiele wird untersucht, ob das Verfahren plausible Lösungen liefert. Des Weiteren dienen die Beispiele um Vergleiche zu anderen bekannten Lösungskonzepten der Spieltheorie durchzuführen.

In der vorliegenden Arbeit wird für zusammenhängende und nicht vollständige Graphen die Caro-Wei-Schranke CW(G) betrachtet. Auf dessen Grundlage wird eine Klassifizierung von Caro-Wei-ähnlichen unteren Schranken für die Unabhängigkeitszahl in Graphen vorgenommen. Außerdem wird eine neue untere Schranke, $\alpha(G) \geq CW(G) + \sum\limits_{v \in V(G)} \sum\limits_{(A,B) \in \pi(v)} \sum\limits_{[A,B,v,\sigma,\tau]\in F(A,B,v)}\frac{1}{c_1\cdots c_{|A|}d_1\cdots d_{|B|}(d(v)+1-|B|)}$, bewiesen. Im Beweis wird der Spezialfall $|A|=|B|=1$ betrachtet und somit die Schranke $\alpha(G) \geq CW(G) + \sum\limits_{v \in V(G)} \sum\limits_{(v,w,u) \in W^2(v)} \frac{1}{|N[v,w,u]| (|N[v,w]|-1) d(v)}$ für induzierte Wege der Länge 2 formuliert. Das daraus entstandene schwächere Theorem wurde vollständig bewiesen.

Die vorliegende Arbeit beschäftigt sich mit einem Optimierungsproblem auf Graphen. Hierbei werden den n Knoten des Graphen G und den zwischen ihnen verlaufenden Kanten positive Zahlenwerte zugeordnet und mit diesen wird eine quadratische Funktion betrachtet. Ziel dieser Arbeit ist es, das Maximum dieser Funktion über dem n-dimensionalen Einheitswürfel zu ermitteln. Die Lösung dieses Problems, die Funktion zu maximieren, ist nicht einfach, da das untersuchte Problem NP-vollständige Unterprobleme enthält. Es wird deutlich, dass im Allgemeinen das Maximum der Funktion durch einen induzierten Untergraphen H von G realisiert wird. Dieser hat je nach Wahl der den Knoten und Kanten zugeordneten Zahlenwerte bestimmte Eigenschaften. Da die explizite Maximierung der Funktion NP-vollständige Probleme als Unterprobleme enthält, wird der Maximalwert in dieser Arbeit als gegeben angenommen. Es wird festgestellt, dass das Maximum in einer Ecke des Einheitswürfels angenommen wird. Mithilfe dieses Resultats wird ein gewisser Untergraph H von G betrachtet, welcher durch bestimmte Knoten des Graphen G induziert werden kann. Wird der Untergraph H zusätzlich minimal gewählt, können weitere Aussagen über den Maximalwert getroffen werden. Durch die verschiedene Wahl der Zahlenwerte an Knoten und Kanten, können gewisse Eigenschaften des Untergraphen H erzwungen werden. Somit werden Resultate erhalten, welche die Existenz von induzierten Untergraphen eines gegebenen Graphen G sichern. Die in den letzten Kapiteln der Arbeit beschriebenen Sätze sagen aus, dass unter gewisser spezieller Wahl der Zahlenwerte an Knoten und Kanten ein induzierter Untergraph H von G mit einem gewissen Maximum existiert, welcher eine gewisse zusätzliche Eigenschaft besitzt. Zum Beispiel ist in bestimmten Fällen die Knotenmenge unabhängig oder die Maximalvalenz beschränkt.