Algorithms and Complexity - Main page Algorithms and Complexity

Seminar: Algorithmische Spieltheorie

Aktuelles


Vorbesprechung: Die Vorbesprechung und Themenvergabe findet erst in der zweiten Vorlesungswoche, am Mittwoch, dem 26.10.2011, statt.

Update (11.10.): Das rege Interesse am Seminar ist sehr erfreulich. Sollten sich mehr als 12 Teilnehmer einschreiben, dann wird es zusätzliche Themen und Sondertermine geben. Die neuen Themen werden bei der Semiarvorbesprechung am 26.10. vorgestellt.

Update (26.10.): Die Vortragsthemen wurden verteilt. Verspätete Anmeldungen für das Seminar sind noch bis zum 09.11. per E-Mail möglich. Die Themen 4, 12 und 13 sind noch verfügbar. Das Seminar beginnt um 13:30 Uhr und findet ab dem 16.11. wöchentlich statt. Es wird einen Zusatztermin im Januar geben.

Update (16.11.): Als Zusatztermin wurde der 11.01.2012, 15-17 Uhr bestimmt.

Bei Anregungen und Fragen zum Seminar wenden Sie sich bitte an Pascal Lenzner.

Termine

SE Mittwoch 13:30 - 15:00 (RUD26 0.313) Albers, Lenzner

Zuordnung

  • Bachelor-/ Master-/ Diplomstudium, Seminar, Theoretische Informatik

Inhalte und Lernziele

Die algorithmische Spieltheorie ist eine neue Forschungsrichtung innerhalb der Theoretischen Informatik, die in den letzten Jahren beträchtliche Aufmerksamkeit erhalten hat. Dies ist dadurch begründet, dass viele aktuelle Probleme nicht von einer zentralen Autorität sondern vielmehr von einer Vielzahl von Agenten zu lösen sind. Beispiele sind insbesondere Probleme, die in großen dezentralen Netzwerken wie dem WWW entstehen. Die Agenten bzw. Spieler verfolgen bei der Wahl ihrer Strategien zum Teil eigennützige Interessen, was starken Einfluss auf die erzielten Problemlöungen hat.
Das Seminar führt in die Thematik ein und behandelt sowohl grundlegende Konzepte, wie z.B. Nash-Gleichgewichte und deren Berechnung, aber auch zahlreiche Probleme in modernen Anwendungen.

Anforderungen

  • regelmäßige Anwesenheit und aktive Mitarbeit
  • Vorlage des fertigen Vortrags beim Betreuer mindestens eine Woche vor dem Vortrag
  • Vortrag (ca. 60 Minuten)
  • Schriftliche Ausarbeitung des Vortrags (etwa acht bis zwölf Seiten, möglichst in LaTeX). Die Ausarbeitung sollte bis zum Ende der Vorlesungszeit vorliegen.

Vortragsthemen

  1. Grundlagen der Spieltheorie --> vergeben!
    Dieser Vortrag soll für alle Seminarteilnehmer das nötige Grundwissen der Spieltheorie bereitstellen. Es werden einige Arten von Spielen vorgestellt und analysiert.
  2. Nash-Gleichgewichte --> vergeben!
    Intuitv ist ein Nash-Gleichgewicht eine Situation in einem Spiel, in der sich keiner der Spieler eigennützlig durch eine Änderung seiner Strategie verbessern kann. Folglich entsprechen solche Gleichgewichte stabilen Situationen, in welchen jeder Spieler "glücklich" ist (genauer gesagt: kein Spieler kann sich im Vergleich zur aktuellen Situation verbessern, falls alle anderen Spieler ihre Strategie beibehalten).
    Nash-Gleichgewichte sind ein zentrales Element der algorithmischen Spieltheorie. Der Grund hierfür ist das berühmte Theorem von John Nash (u.a. die Hauptfigur des Films "A beautiful mind"), welches besagt, dass jedes endliche Spiel ein (gemischtes) Nash-Gleichgewicht besitzt.
    In diesem Vortrag werden wir uns auf die Spuren dieses nobelpreiswürdigen (Nash erhielt 1994 den Nobelpreis für Wirtschaftswissenschaften dafür) Theorems begeben.
  3. Berechnung und Komplexität von Nash-Gleichgewichten --> vergeben!
    Nash-Gleichgewichte haben leider einen gravierenden "Schönheitsfehler": Es ist im Allgemeinen sehr schwierig sie zu berechnen. In diesem Vortrag beschäftigen wir uns mit einigen positiven Ausnahmen dieser Regel und mit dem Lemke-Howson-Algorithmus. Wir betrachten aber auch die negativen Seiten, indem wir einen kurzen Blick auf Härteresultate für gewisse Spiele werfen.
  4. Network Creation Games
    Wir alle haben täglich mit Netzwerken Kontakt. Zum Beispiel soziale Netzwerke, Verkehrsnetzwerke oder Kommunikationsnetzwerke. Doch wie entstehen solche Netzwerke eigentlich? Und welche Netzwerke entstehen, wenn eigennützige (geizige) Agenten im Spiel sind, die ein möglichst gutes Netzwerk nutzen wollen, jedoch dafür nur so wenig wie möglich beizutragen bereit sind? Es haben sich zwei Forschungsrichtungen für diese Spiele etabliert und hier betrachten wir die sogenannten Network Creation Games.
  5. Network Formation Games --> vergeben!
    Ähnlich wie bei den Network Creation Games, geht es hier um Netzwerkspiele. Wir betrachten die zweite Forschungsrichtung die sich mit solchen Spielen beschäftigt.
  6. Selfish Routing --> vergeben!
    Auf Berlins Straßen passiert immer morgens und abends Folgendes: Viele Autofahrer versuchen eine gewisse Strecke innerhalb der Stadt zurückzulegen, wobei jeder versucht die beste (schnellste) Route zum Ziel zu wählen. Falls diese Routen keine gemeinsamen Staßen benutzen, dann gibt es keine Probleme. Benutzen mehrere Autos die selbe Straße, dann kommt es ab einer gewissen Anzahl von Autos zu Verzögerungen oder gleich zum Stau. Die Routenwahl hängt folglich stark mit der Routenwahl der anderen Verkehrsteilnehmer zusammen. Genau dieses Szenario wird mit den Routing Spielen modelliert und wir betrachten die Auswirkungen des eigennützigen Verhaltens der Verkehrsteilnehmer etwas genauer.
  7. Mechanismen & Auktionen --> vergeben!
    Mechanismen sind spezielle Algorithmen, die Inputs von allen Spielern erhalten und damit etwas berechnen. Diese Algorithmen sollten jedoch auch dann zuverlässig arbeiten, wenn alle Spieler eigennützig handeln und jeder versucht den Algorithmus auszutricksen um einen Vorteil zu erhalten.
    In diesem Vortrag lernen wir den Bereich des "mechanism design" näher kennen und setzen uns am Beispiel von Auktionen mit verschiedenen Mechanismen auseinander. Es gibt viele Auktionssysteme mit unterschiedlichen Eigenschaften und wir begeben uns auf die Suche nach dem bestmöglichen. Wir werden dabei eine weitere (wirtschafts-)nobelpreiswürdige Idee antreffen.
  8. Wahlsysteme --> vergeben!
    Wir bleiben in der Welt der Mechanismen und widmen uns dem Gebiet der "Social Choice Probleme". Diese beschäftigen sich damit, wie eine Vielzahl von (eigennützigen) Agenten eine (gute) Entscheidung treffen kann. Ein Beispiel hierfür sind Wahlsysteme. Es gibt viele unterschiedliche Wahlsysteme mit jeweils unterschiedlichen Vor- und Nachteilen. Eine etwas andere Sonntagsfrage lautet somit wie folgt: "Angenommen nächsten Sonntag sind Bundestagswahlen, welches Wahlsystem sollte benutzt werden?"
    In diesem Vortrag suchen wir nach einer passenden Antwort.
  9. Mechanismen ohne Geld --> vergeben!
    Viele Mechanismen erreichen ihre guten Eigenschaften durch Belohnungs- und Bestrafungssysteme (meist in Form vom Geld). In diesem Vortrag betrachten wir Mechanismen für spezielle Probleme, die ohne diesen Trick auskommen.
  10. Matching Markets & Markets with Intermediaries --> vergeben!
    In diesem Vortrag beschäftigen wir uns mit Zuweisungsproblemen. Solche Probleme sind allgegenwärtig, zum Beispiel wenn Studenten zu Wohnheimzimmern oder (indirekt durch Preise) Käufer zu Verkäufern zugewiesen werden sollen. Wir beschäftigen uns damit, wie eine möglichst gute Zuweisung berechnet werden kann und begegnen dabei einem sehr eleganten Algorithmus. Im Szenario mit Käufern und Verkäufern werden wir uns mit dem Problem auseinandersetzen, wie die Preise festgelegt werden müssen, damit alle Verkäufer ihre Ware verkaufen können und jeder Käufer zufrieden ist. Tatsächlich gibt es immer solche Preise und diese können mit Hilfe einer speziellen Auktion bestimmt werden.
    Weiterhin werden wir uns der Frage widmen, was passiert, wenn der Handel nicht direkt, sondern über Zwischenhändler (Intermediaries) abgewickelt wird.
  11. Ranking & Websearch --> vergeben!
    Rankingprobleme sind Social Choice Probleme. Eine spezielle Anwendung davon ist Google's berühmter PageRank-Algorithmus. Nach einer kurzen Einführung in Rankingsysteme und in die Struktur des WWW werden wir uns aus unterschiedlichen Blickwinkeln mit dem PageRank-Algorithmus auseinandersetzen.
  12. Sponsored Search Markets
    Sucht man mit Hilfe einer Suchmaschine nach einem bestimmten Begriff, dann erscheinen außer den Suchergebnissen meist auch inhaltlich passende Werbeanzeigen. Die Idee der gezielten Werbung ist dabei so erfolgreich, dass z.B. Google den Großteil seiner Einnahmen über die Versteigerung dieser Werbeplätze erzielt. Wir beschäftigen uns in diesem Vortrag etwas genauer mit solchen Mechanismen.
  13. Selfish Load Balancing
  14. Kooperative Spiele --> vergeben!
  15. Cost-Sharing --> vergeben!
  16. Bargaining and Power in Networks --> vergeben!

Vortragstermine

Termin Vortragende(r) Titel
19.10.2011 -
26.10.2011 Vorbesprechung und Themenvergabe
02.11.2011 -
09.11.2011 -
16.11.2011 Antje Schulz Grundlagen der Spieltheorie
23.11.2011 Robert Winkler Nash-Gleichgewichte
30.11.2011 Denis Erfurt Berechnung und Komplexität von Nash-Gleichgewichten
07.12.2011 Jonathan Sielhorst Network Formation Games
14.12.2011 Steffen Kaden Selfish Routing
04.01.2012 Florian Tornow Mechanismen & Auktionen
11.01.2012 Markus Matzker Kooperative Spiele
11.01.2012 Dan Hachenberger Cost-Sharing
18.01.2012 Andre Kiessling Wahlsysteme
25.01.2012 Anna-Lisa Deussing Mechanismen ohne Geld
01.02.2012 Daniel Hartmann Matching Markets & Markets with Intermediaries
08.02.2012 Axel Mosch Bargaining and Power in Networks
15.02.2012 Martin Münn Ranking & Websearch

Literatur

Hauptliteratur

  • N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani. Algorithmic Game Theory. Cambridge University Press. ISBN: 9780521872829
    Eine online-Version dieses Buches ist kostenlos hier erhältlich. (username=agt1user, password=camb2agt)
  • Y. Shoham, K. Leyton-Brown. Multiagent Systems. Cambridge University Press. ISBN: 9780521899437
    Die PDF-Version dieses Buches ist kostenlos hier erhältlich.
  • D. Easley, J. Kleinberg. Networks, Crowds and Markets. Cambridge University Press. ISBN: 9780521195331
    Die PDF-Version dieses Buches ist kostenlos hier erhältlich.

Ergänzende Literatur

  • Y. Shoham. Computer science and game theory. Communications of the ACM. Volume 51/8. 2008
  • T. Roughgarden. Algorithmic game theory. Communications of the ACM. Volume 53/7. 2010
  • Fairness, Kooperation, Demokratie. Spektrum der Wissenschaft - Dossier 5/2006. Spektrum-Verlag

Links



Bei Anregungen und Fragen zum Seminar wenden Sie sich bitte an Pascal Lenzner.
last modified 11/16/11 (alkox-www)