Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Hauptinhalt

Algorithmische Spieltheorie

im Sommersemester 2017



Veranstalter:Jun.-Prof. Dr. Thomas Kesselheim
Termine: VorlesungMontag10:15-12:00 Uhr OH12-1.056
ÜbungDonnerstag10:15-12:00 UhrOH14-E02 OH14-304
Beginn: Montag, den 24.04.2017


[Aktuelles] [Zusammenfassung] [Materialien] [Übungsblätter] [Literatur]


Aktuelles

<b>NEU</b> Das erste Übungsblatt ist jetzt online. Siehe auch die Hinweise zur Abgabe unten.
<b>NEU</b> Anders als ursprünglich angekündigt, finden die Donnerstagstermine im Raum OH14-304 statt.
<b>NEU</b> Am Donnerstag, den 27.04.2017 findet anstatt der Übung eine Vorlesung statt.
<b>NEU</b> Die Vorlesung beginnt am Montag, den 24.04.2017.


Zusammenfassung

Überall in der Welt moderner Computernetzwerke gibt es Situationen, in denen sich die Beteiligten strategisch verhalten. Ein Beispiel sind Internet Service Provider, die ihre Pakete möglichst kostengünstig zustellen möchten. Ein anderes sind cloud-basierte Dienste: Endnutzer und Dienstanbieter mieten Infrastruktur für Berechnungen. Hierdurch entsteht ein riesiger, elektronischer Markt. Schließlich möchten auch Anzeigenkunden ihr Zielpublikum möglichst günstig erreichen. Dies ist die Grundlage des Geschäftsmodells der weltgrößten Firmen.

In all diesen Szenarien agieren Algorithmen als strategische Agenten oder müssen mit strategischem Verhalten umgehen. Dies führt zu Fragen über die übliche Algorithmentheorie hinausgehen. Algorithmische Spieltheorie, eine junge Forschungsrichtung an der Schnittstelle zwischen Spieltheorie und Algorithmik, bietet mögliche Antworten auf diese Fragen. Auf der einen Seite bedeutet dies, vorhandene Ansätze und Systeme zu analysieren und zu erklären. Auf der anderen Seite geht es aber auch um Entwicklung neuer Systeme, so dass sie mit strategischem Verhalten umgehen können.

In dieser Veranstaltung werden wir die Grundlagen Algorithmischer Spieltheorie behandeln, insbesondere

  • Grundlagen der Spieltheorie
  • Berechenbarkeit von Gleichgewichten
  • Konvergenz von Dynamiken strategischer Agenten
  • Verluste durch strategisches Verhalten
  • Entwurf von Anreiz-kompatible Marktmechanismen
  • Auktionen und andere Mechanismen zur Umsatz- oder Gewinnmaximierung


Es handelt sich um eine Theorievorlesung. Das heißt, alle Ergebnisse werden formal bewiesen. Voraussetzung ist ein grundsätzliches Verständnis von Algorithmentheorie. Vorkenntnisse in Spieltheorie sind nicht erforderlich.


Materialien

Übungsblätter

  • 1. Übungsblatt
    Wegen des Feiertags gebt die Lösungen diesmal bitte in Büro 315, Otto-Hahn-Str. 14, ab. Alternativ könnt ihr sie auch in Briefkasten 22 im Erdgeschoss Otto-Hahn-Str. 14 (eigentlich für DAP2-Übungsgruppen 4, 13, 23) einwerfen. In jedem Fall sollten die Abgaben natürlich beschriftet sein.
    Abgabe der Lösungen bis zum 02.05.2017, 12 Uhr in Gruppen von bis zu drei Studierenden
  • 2. Übungsblatt, Abgabe am 08.05.2017

Literatur


Die Literaturangaben werden demnächst bekannt gegeben.

Letzte Änderung am 27.04.2017 von T. Kesselheim