Wolfgang Mulzer, Yannik Stein
Termin: Dienstags, 16–18 Uhr, SR 006

Voraussetzungen

• Schein in "Höhere Algorithmik", "ALP 3" oder vergleichbarer Veranstaltung
• Vordiplom in Informatik, Mathematik o.ä. oder vier erfolgreiche Semester im BSc-Studiengang.

Scheinkriterien

• erfolgreicher Vortrag, insgesamt 90 Minuten Dauer.
• Kurzbeschreibung des Vortrags, ca. 4 DIN A4-Seiten in PDF. Davon sind vor dem Vortrag Kopien an alle Teilnehmer auszuteilen und ein elektronisches Exemplar abzugeben. Hier ist eine LaTex-Vorlage.
• Regelmäßige Teilnahme am Seminar (max. 4 Fehltermine).

• 06.02.2014: Am 18.02 findet das Seminar von 14.30–18.30 im Raum SR 049 in der Takustr. 9 statt.
• 28.01.2014: Heute fällt das Seminar aus.
• 20.10.2013: Es gibt eine LaTex-Vorlage für die Zusammenfassung.
• 20.09.2013: Der erste Vortrag findet statt am 15.10.2013. Nadja Scharf gibt eine Einführung in die Spieltheorie.
• 08.07.2013: Die Vorbesprechung findet statt am Donnerstag, den 11.07.2013, Raum SR 051, 16:00 Uhr ct.
• 29.06.2013: Die Themenliste ist online.

Das Seminar befasst sich mit algorithmischer Spieltheorie. Mithilfe von Spielen kann die Interaktion mehrerer Individuen, mit unterschiedlichen Interessen, modelliert werden. So können z.B. Wirtschaftssysteme und Computernetzwerke mathematisch abgebildet werden. Von besonderem Interesse ist die Berechnung spezifischer Eigenschaften der Spiele, wie stabile Zustände (Equilibria) oder optimale Strategien. Wir werden uns einen Überblick über die verschiedenen Arten von Spielen verschaffen und verwandte algorithmische Probleme und deren Komplexität besprechen.

• 7. Mechanism Design

  Ein Mechanismus ist ein Verfahren, in dem Individuen mit unterschiedlichen Interessen miteinander agieren (z.B. Wahlen, Märkte, Auktionen). Ziel ist der Entwurf von Mechanismen, die bestimmte Anforderungen erfüllen.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 9. [link]

• 9. Entwurf von Effizienten Mechanismen

  Wir wollen Mechanismen zusätzlich so entwerfen, dass zugehörige algorithmischen Probleme effizient lös- bzw. approximierbar sind. Dies kann im Widerspruch zu ihrem eigentlichen Ziel, Anreize für ein bestimmtes Verhalten der Spieler zu schaffen, stehen.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 12. [link]

• 11. Online Mechanismen

  Mechanismen in einem dynamischen Universum: Spieler können aus dem Spiel aussteigen/einsteigen und zukünftige Entscheidungsmöglichkeiten sind unbekannt. Es gibt verschiedene Algorithmen, um in dynamischen Mechanismen Entscheidungen zu treffen.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 16. [link]

Bereits vergeben:

• 1. Einführung in die Spieltheorie

  Literatur:

  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 1. [link]
  • Rothe, Baumeister, Lindner, Rothe. Einführung in Computational Social Choice. [link] (abrufbar aus dem Uni-Netz)

• 2. Die Komplexitätsklasse PPAD

  PPAD ist eine Komplexitätsklasse zwischen (F)P und (F)NP, für die ein wichtiges Problem aus der Spieltheorie (2-Spieler Nash-Equilibrium) vollständig ist.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 2. [link]

• 3. 2-Nash Algorithmen

  Nash-Equilibria können mithilfe des Lemke-Howson Algorithmus in 2-Spieler Spielen berechnet werden. Ist das Spiel in einer bestimmten Form gegeben (extensiver Normalform), kann u.U. die Laufzeit durch Berechnung von Equilibria für Teilspiele verbessert werden.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 3. [link]

• 4. Regret Minimization

  Entscheidungen müssen in unsicheren Umgebungen getroffen werden, d.h. Strategien müssen ausgewählt werden, obwohl die Bewertungsfunktion unbekannt ist. Der Regret einer Strategiewahl ist die Differenz des Ergebnisses zu dem Ergebnis der Strategie eines oder mehrerer Referenzalgorithmen. Ziel ist es Algorithmen zu entwickeln, die den Regret minimieren.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 4. [link]

• 5. Market Equilibria

  Ein Market Equilibrium ist die Preisfestlegung aller Waren auf einem Markt, so dass alle zu einem höchstmöglichen Preis verkauft werden (Angebot = Nachfrage). Es existieren Polynomialzeit Algorithmen zur Berechnung von Market Equilibria im Fisher und Arrow-Debreu Model.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 5. [link]

• 6. Graphische Spiele

  Die Spiele sind als Graph gegeben: Spieler bilden die Knoten und Kanten stellen Abhängigkeiten in der Zielfunktion der Spieler dar. Diese zusätzlichen Informationen können algorithmisch verwendet werden.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 7. [link]

• 8. Kombinatorische Auktionen

  In kombinatorischen Auktionen kann auf Mengen von Gegenständen, anstatt auf nur einen einzigen Gegenstand, gleichzeitig geboten werden. So können Abhängigkeiten zwischen den Gegenständen modelliert werden. Ziel ist es, die Gewinner der Gegenstände algorithmisch so zu bestimmen, dass die Zufriedenheit unter allen Bietern maximal ist.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 11. [link]

• 10. Kooperative Spiele

  In kooperativen Spielen gibt es Anreize für Spieler zusammen zu arbeiten. Beispielsweise können sich mehrere Spieler die Kosten für die Benutzung einer Ressource teilen.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 15. [link]

• 12. Network Formation Games

  Network Formation Games sind Spiele, die Computernetzwerke simulieren. Es sollen verschiedene Varianten vorgestellt und analysiert werden.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 19. [link]

• 13. Price of Anarchy

  Der Preis der Anarchie in einem Mechanismus ist die Differenz zwischen der Summe der erzielten Gewinne, wenn alle Spieler egoistisch handeln, und der Summe der erzielten Gewinne, wenn alle Spieler zusammen arbeiten. Durch Anpassungen des Mechanismus kann die Differenz minimiert werden.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 21. [link]

• 14. Peer-to-Peer Systeme

  Peer-to-Peer Systeme müssen so entworfen werden, dass es für die Teilnehmer Anreize gibt, ihre lokalen Ressourcen mit anderen Teilnehmern zu teilen. Es sollen verschiedene Methoden vorgestellt werden, dies zu erreichen.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 23. [link]

• 15. Prediction Markets

  Prediction Markets aggregieren Wissen und Meinungen von vielen Individuen um Vorhersagen über zukünftige Ereignisse zu treffen. Dabei gibt es verschiedene Methoden wie das Wissen zusammengeführt wird.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 26. [link]

• 16. Reputation Systems

  Reputationssysteme bewerten die Zuverlässigkeit der Teilnehmer. Es gibt verschiedene Ansätze, um solche Systeme gegenüber Manipulationen zu schützen.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 27. [link]

• 17. Computational Evolutionary Game Theory

  Evolutionary Game Theory modelliert die Vererbung von Strategien/Verhaltensweisen in Populationen. Es soll eine Einführung gegeben und verwandte algorithmische Probleme vorgestellt werden.

  Literatur: Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, Kapitel 29. [link]

• 18. Cake Cutting (1. Teil)

  Ein Kuchen soll unter Kindern so aufgeteilt werden, dass es alle Kinder als fair empfinden. Jedes Kind hat allerdings eine eigene, nicht notwendigerweise deterministische, Maßfunktion für die Größe der Kuchenstücke. Es gibt verschiedene Varianten des Problems mit zugehörigen Algorithmen, die faire Schnitte berechnen bzw. approximieren.

  Literatur:

  • Rothe, Baumeister, Lindner, Rothe. Einführung in Computational Social Choice. [link] (abrufbar aus dem Uni-Netz)
  • Procaccia, Brandt, Conitzer, Endriss, Lang. Cake Cutting Algorithms. [link] (draft)
  • Jack Robertson, William Webb. Cake cutting algorithms: be fair if you can.

• 19. Cake Cutting (2. Teil)

  Ein Kuchen soll unter Kindern so aufgeteilt werden, dass es alle Kinder als fair empfinden. Jedes Kind hat allerdings eine eigene, nicht notwendigerweise deterministische, Maßfunktion für die Größe der Kuchenstücke. Es gibt verschiedene Varianten des Problems mit zugehörigen Algorithmen, die faire Schnitte berechnen bzw. approximieren.

  Literatur:

  • Rothe, Baumeister, Lindner, Rothe. Einführung in Computational Social Choice. [link] (abrufbar aus dem Uni-Netz)
  • Procaccia, Brandt, Conitzer, Endriss, Lang. Cake Cutting Algorithms. [link] (draft)
  • Jack Robertson, William Webb. Cake cutting algorithms: be fair if you can.

(Die Zusammenfassungen und Folien der Teilnehmer sind ohne Gewähr der Richtigkeit.)

Datum	Sprecher	Thema	Zusfsg.	Folien
15.10.2013	Nadja Scharf	Einführung in die Spieltheorie
22.10.2013	Oliver Wiese	Die Komplexitätsklasse PPAD
29.10.2013	Katharina Klost	2-Nash Algorithmen
05.11.2013	Alexander Kauer	Regret Minimization
12.11.2013	Sebastian Stugk	Market Equilibria
19.11.2013	Michael Brückner	Graphische Spiele
26.11.2013	Wolfgang Mulzer	Mechanism Design
03.12.2013	Olaf Parczyk	Kombinatorische Auktionen
10.12.2013	Christian Hofmann	Kooperative Spiele
07.01.2014	Robert L. Gottwald	Network Formation Games
14.01.2014	Max-Peter Wisniewski	Price of Anarchy
21.01.2014	Marcel Ehrhardt	Peer-to-Peer Systeme
28.01.2014	fällt aus
04.02.2014	Adam Furmańczuk	Reputation Systems
11.02.2014	Julian Ritter	Computational Evolutionary Game Theory
18.02.2014	Tawatchai Siripanya	Prediction Markets
18.02.2014	Simon Tippenhauer	Cake Cutting

Wie halte ich einen Vortrag?

Im Web gibt es viele Ressourcen mit nützlichen Tipps zur effektiven Gestaltung eines Vortrags. Hier einige Beispiele, die mir gefallen haben.

1. Christian Knauer und Frank Hoffmann.
   Wie gestalte ich einen Seminarvortrag?
   Etwas alt, aber immer noch interessant.
2. Ian Parberry.
   How to Present a Paper in Theoretical Computer Science: A Speaker's Guide for Students.
   Spezielle Tipps für die theoretische Informatik.
3. Paul Halmos.
   How to talk Mathematics.
   Für Mathematiker, aber vieles trifft auch auf die theoretische Informatik zu.
4. Patrick Winston.
   How to speak.
   Lustiges Video. Die ersten fünf Minuten kann man getrost überspringen.

Hier die Fragen, von denen wir uns bei der Bewertung eines Seminarvortrags leiten lassen.

Im Anschluss an die Veranstaltung können Studien–, Bachelor–, Examens–, Diplom– und Masterarbeiten vergeben werden.