Algorithmische Spieltheorie

Julian Nickerl; Florian Sihler; Jacobo Torán

doi:10.58662/9783965435865

Zusammenfassung

Die Vorlesung Algorithmische Spieltheorie findet seit dem Sommersemester 2014 jährlich an der Universität Ulm statt, eingebunden im Lehrangebot des Instituts für Theoretische Informatik. Gemeinsam eingeführt von Prof. Uwe Schöning und Prof. Jacobo Torán, wurde die Vorlesung stets weiterentwickelt. Seit einigen Jahren existiert ein von Prof. Torán und seinem damaligen Promotionsstudenten Dr. Julian Nickerl erweitertes Skript. Im Sommersemester 2021 verwendet der Masterstudent Florian Sihler seine Vorlesungsmitschriften für ein noch ausführlicheres Skript – Grundlage für dieses Buch. Zielgruppe sind Studierende im Bereich Informatik im Master sowie höheren Bachelorsemestern. Einige Grundlagen des Informatikstudiums werden vorausgesetzt, insbesondere Begriffe und Notation aus Mathematik und Komplexitätstheorie. Zudem ist das Buch primär ein Überblick über viele verschiedene Themenbereiche der algorithmischen Spieltheorie. Weiterhin legen wir in unserem Institut besonderen Wert auf Themen im Bereich der Komplexitätstheorie. Diese werden daher umfassender behandelt als in ähnlichen Publikationen. Die Vorlesung Algorithmische Spieltheorie ist inzwischen eine der am besten besuchten Veranstaltungen im weiterführenden Lehrangebot des Instituts für Theoretische Informatik. Wir hoffen, durch dieses Buch ein ähnliches Interesse sowohl außerhalb von Hochschulen zu wecken, als auch Lehrenden ein Werkzeug an die Hand zu geben, dieses spannende Themenfeld in ihren Lehrplan einzubinden.

Schlagworte

Publikation durchsuchen

Bibliographische Angaben

Auflage: 1/2025
Copyrightjahr: 2025
ISBN-Print: 978-3-96543-579-7
ISBN-Online: 978-3-96543-586-5
Verlag: Lehmanns Media, Berlin
Sprache: Deutsch
Seiten: 127
Produkttyp: Monographie

Inhaltsverzeichnis

KapitelSeiten

1. Inhaltsverzeichnis Kein Zugriff
1. 1. 1.1.1 Battle of the Sexes Kein Zugriff
  2. 1.1.2 Das Gefangenendilemma Kein Zugriff
  3. 1.1.3 Das Braess-Paradoxon Kein Zugriff
  4. 1.1.4 Das Netzwerkverbindungsspiel Kein Zugriff
  5. 1.1.5 Sponsored Auctions Kein Zugriff
1. 1. 2.1.1 Entscheidungsprobleme Kein Zugriff
  2. 2.1.2 Das Konzept der Reduzierbarkeit Kein Zugriff
  3. 2.1.3 Suchprobleme Kein Zugriff
  4. 2.1.4 Optimierungsprobleme Kein Zugriff
2. 1. 2.2.1 Dominanz Kein Zugriff
  2. 2.2.2 Nash-Gleichgewicht Kein Zugriff
  3. 2.2.3 Gemischte Strategien Kein Zugriff
1. 3.1 Reine Strategien als beste Antworten Kein Zugriff
2. 3.2 2 × 2-Matrixspiele Kein Zugriff
3. 1. 3.3.1 Analyse von 2 × 2-Spielen Kein Zugriff
  2. 3.3.2 Ein algebraischer Ansatz für 2 × 2 Spiele Kein Zugriff
4. 1. 3.4.1 Das Dualitätsprinzip Kein Zugriff
  2. 3.4.2 Der Übergang zur Spieltheorie Kein Zugriff
5. 3.5 Zurück zu allgemeinen Matrixspielen Kein Zugriff
6. 1. 3.6.1 Polynomial Parity Arguments on Directed Graphs (ppad) Kein Zugriff
1. 1. 4.1.1 Darstellungen Kein Zugriff
2. 1. 4.2.1 Teilspiele Kein Zugriff
  2. 4.2.2 Teilspielperfektion Kein Zugriff
  3. 4.2.3 Analyse von Zermelos’ Algorithmus Kein Zugriff
3. 1. 4.3.1 Die reduzierte Strategische Form Kein Zugriff
  2. 4.3.2 Die sequenzbasierte Beschreibung Kein Zugriff
1. 1. 5.1.1 Einige Beispiele Kein Zugriff
2. 1. 5.2.1 Ein Beispiel – WQBF Kein Zugriff
  2. 5.2.2 geo Kein Zugriff
1. 1. 6.1.1 Ein beispielhaftes Congestion-Spiel Kein Zugriff
2. 6.2 Nash-Gleichgewichte Kein Zugriff
3. 1. 6.3.1 Potentialfunktionen Kein Zugriff
  2. 6.3.2 Potentialspiele Kein Zugriff
  3. 6.3.3 Beispiele Kein Zugriff
  4. 6.3.4 Potentialspiele und Congestion-Spiele Kein Zugriff
4. 1. 6.4.1 Pos-NAE-2Sat und ein Beispiel einer Reduktion Kein Zugriff
  2. 6.4.2 Finden von reinen Nash-Gleichgewichten in Congestion-Spielen und pls Kein Zugriff
5. 1. 6.5.1 Symmetrische Netzwerk-Congestion-Spiele Kein Zugriff
  2. 6.5.2 Finden eines Nash-Gleichgewichts in polynomieller Zeit Kein Zugriff
  3. 6.5.3 Matroid-Congestion-Spiele Kein Zugriff
6. 1. 6.6.1 Nash-Gleichgewichte und Potentiale Kein Zugriff
1. 7.1 Preis der Anarchie und Stabilität Kein Zugriff
2. 7.2 Job Scheduling Kein Zugriff
3. 1. 7.3.1 Reine Nash-Gleichgewichte Kein Zugriff
  2. 7.3.2 Faire Netzwerkverbindungsspiele Kein Zugriff
4. 7.4 Starke Nash-Gleichgewichte Kein Zugriff
1. 1. 8.1.1 strategy-proof Kein Zugriff
  2. 8.1.2 Weitere Eigenschaften von Mechanismen Kein Zugriff
  3. 8.1.3 VCG-Mechanismen Kein Zugriff
  4. 8.1.4 Beispiele Kein Zugriff
2. 8.2 Sponsored Search Kein Zugriff
3. 8.3 Matching Markets Kein Zugriff
Literatur Kein Zugriff Seiten 126 - 126