Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

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] [Prüfung] [Literatur]


Aktuelles

<b>NEU</b> Anscheinend ist die All-Pay Auction nicht (1/3, 1)-smooth im Sinn der Vorlesung. Sie ist aber (1/2, 2)-smooth. Hier der Beweis.
<b>NEU</b> Nicht abgeholte Übungslösungen können umgehend abgeholt werden. Im kommenden Semester werden alle verbleibenden entsorgt.
<b>NEU</b> Anmerkungen zur Prüfung: Ein sehr wichtiges Lernziel ist es, Konzepte kennenzulernen. Deshalb ist es auch wichtig, die Definitionen gut zu kennen, und erklären zu können. Wichtig ist weiterhin, welche Zusammenhänge es gibt, welche Sätze wir gezeigt haben, und wie wir dabei vorgegangen sind. Einige Beweise bestehen aus längeren Rechnungen (ganz besonders in Vorlesungen 4, 11 und 13). Diese Rechnungen müssen in der Prüfung nicht wiedergegeben werden können, wohl aber die Idee, wo sie anfängt, aufhört, was sie benutzt.
Wie bei jeder mündlichen Prüfung ist es sehr sinnvoll, sich mit Kommiliton*innen gemeinsam vorzubereiten. Gerade Studierende, die sich lieber alleine vorbereiten, sollten üben, Konzepte zu erklären. Es hilft, typische Fragen laut gesprochen zu beantworten — auch wenn niemand dabei zuhört.
<b>NEU</b> Bitte jetzt einen Prüfungstermin per E-Mail vereinbaren.



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

Als Studienleistung müssen insgesamt 50 % der Punkte in den Übungen erzielt werden.
  • 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
    Update 04.05.: Aufgabe 3 wurde präzisiert
  • 3. Übungsblatt, Abgabe am 15.05.2017
  • 4. Übungsblatt, Abgabe am 29.05.2017
  • 5. Übungsblatt, Abgabe am 06.06.2017
  • 6. Übungsblatt, Abgabe am 19.06.2017
  • 7. Übungsblatt, Abgabe am 26.06.2017
  • 8. Übungsblatt, Abgabe am 03.07.2017
  • 9. Übungsblatt, Abgabe am 10.07.2017
    Update 08.07.: Aufgabe 3a wurde präzisiert
  • 10. Übungsblatt, Abgabe am 17.07.2017
  • 11. Übungsblatt, Abgabe am 24.07.2017

Prüfung

Die Modulprüfung ist mündlich. Termine werden individuell vereinbart. Zur Wahl stehen folgende Zeiträume

  • Anfang August (01.08.)
  • Mitte August (15.-16.08., 22.-24.08.)
  • Ende August (29.-31.08.)
  • Mitte September (13.-14.09.)
Bitte kontaktiert Thomas per E-Mail zur Terminvereinbarung, unter Angabe von Terminwünschen.



Letzte Änderung am 31.07.2017 von T. Kesselheim