50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Algorithmische Spieltheorie


This page was taken from an older version of this website.

Termine

Vorbesprechung und Themenvergabe
Mi, 20.10.2004, 14 Uhr ct, Seminarraum Informatik 4 (Minsky)
Zeit und Ort der Veranstaltung
Mittwoch, 14 Uhr ct, Seminarraum Informatik 4 (Minsky)

Formalitäten

Art der Lehrveranstaltung
Hauptseminar (2 SWS, 3 ECTS-Punkte)
Einordnung
Diplomstudiengang Informatik, Wahlpflichtmodul
Bachelorstudiengang Informatik, 5. Semester
Masterstudiengang Informatik
Vortragssprache
Diplom: Deutsch
Bachelor/Master: Englisch
Bedingungen zur erfolgreichen Teilnahme
- einstündiger Vortrag basierend auf einer wissenschaftlichen Arbeit in englischer Sprache
- kurze schriftliche Zusammenfassung der vorgestellten Arbeit
- Teilnahme an den anderen Vorträgen

Inhalt

Kurzbeschreibung

In immer mehr Netzwerkanwendungen wird das Systemverhalten vom egoistischen Handeln ihrer Nutzer bestimmt, z.B. in Internet-Tauschbörsen, Online-Auktionen und Pay-per-view Diensten.

Die algorithmische Spieltheorie untersucht, wie man Anwendungen so entwirft, dass sie trotz des egoistischen Verhaltens der einzelnen Nutzer für die Gesamtheit so nützlich wie möglich sind.

In diesem Seminar geben wir einen einführenden Einblick in das Gebiet und diskutieren einige ausgewählte Probleme im Detail.

Detailliertere Beschreibung des Gebiets

Im 18. Jahrhundert begann man, wirtschaftliches Handeln in Form von Spielen zu modellieren und diese mathematisch zu untersuchen. Die moderne Spieltheorie wurde maßgeblich in den 1920er bis 1950er Jahren durch John von Neumann und John Nash geprägt (letzterer bekannt geworden durch den Kinofilm "A Beautiful Mind").

Wurde die Spieltheorie zunächst hauptsächlich auf strategische Fragestellungen des Kalten Krieges angewandt, so führte ihre Weiterentwicklung in den 70er Jahren zu einer Revolution in den Wirtschaftswissenschaften. Zudem wurden neue Anwendungsfelder wie Soziologie und Biologie für die Spieltheorie entdeckt.

Seit den 1980er Jahren entwickelt sich das Internet rasant zu einem gigantischen sozio-ökonomischen Netzwerk, das eine Plattform für neuartiges wirtschaftliches Handeln bietet. Hierdurch ist das gegenseitige Interesse von Wirtschaftswissenschaften und Informatik gestiegen.

Im Seminar sollen behandelt werden:

Distributed Algorithmic Mechanism Design
Durch die hohe Verfügbarkeit des Internets ergeben sich neue Möglichkeiten, wirtschaftliche Handlungsvorgänge (so genannte "Mechanismen") zu gestalten (z.B. Online-Auktionen, Pay-per-View-Dienste). Allerdings ergibt sich aus der Dezentralität des Internets die große Herausforderung, dafür zu sorgen, dass die Mechanismen zum Einen effizient ausgeführt und zum Anderen nicht (aufgrund egoistischer Interessen) manipuliert werden können. Insbesondere wird untersucht, wie man die Spieler dazu bewegen kann, ihre tatsächlichen Interessen preiszugeben.

Digital Goods, Multicast-Transmissions
Digitale Wirtschaftsgüter (Textdokumente, Bilder, Videos, Software etc.) besitzen zum Teil völlig andere Eigenschaften als "klassische" Güter, wie zum Beispiel leichte Kopierbarkeit, ständige Verfügbarkeit, geringe oder keine Transportkosten. Wie legt man hier vernünftige Preise fest?

Interdomain Routing
Mit der zunehmenden Auslastung des Internets stellt sich die Frage, wie die bestehenden Ressourcen (etwa verschiedene Datenrouten mit unterschiedlichen Übertragungsraten) und die entstehenden Kosten auf die Nutzer verteilt werden sollten. Hierzu muss die Interaktion zwischen Netzbetreibern, Service-Anbietern und Nutzern modelliert und analysiert werden.

Equilibria
Dies sind globale Zustände, die bei simultanem egoistischen Verhalten der Spieler angestrebt werden. In einem Gleichgewichtszustand sind alle Spieler hinreichend "zufrieden". In Netzwerkanwendungen müssen Gleichgewichte online berechnet werden. Kann man dies auch immer effizient lösen?

Selfish Resource Allocation, Price of Anarchy
Könnte eine zentrale Autorität den Netzwerk-Teilnehmern ihr Verhalten vorschreiben, so ließe sich stets das größtmögliche Gemeinwohl erreichen. Allerdings verhalten sich die Teilnehmer in der Regel egoistisch, so dass sich suboptimale Gleichgewichtszustände einstellen können. Wie hoch ist der Verlust, der durch das dezentrale egoistische Verhalten in Kauf genommen werden muss? Was ist der "Preis der Anarchie"? Wie lässt sich dieser Preis möglichst gering halten?

Vorträge

Datum Vortragender Titel Unterlagen
10.11.2004 Hagen Völzer Grundlagen: Spiele - Auktionen - ... .pdf
17.11.2004 Hagen Völzer Grundlagen: ... - Mechanismen
24.11.2004 Fabian Hezel Worst-Case Equilibria
19.01.2005 Andreas Horn BGP-based Lowest-Cost Routing
26.01.2005 Hervé Hounnang Selfish Routing
09.02.2005 Matthias Schmalz Computation of Equilibria

Vortragsthemen und Literatur:

Grundlagen
1. Klassische Spieltheorie, Mechanismen-Entwurf und Auktionen
Papadimitriou: Algorithms, Games, and the Internet
Osborne: An introduction to game theory, Kapitel 1 bis 3
Sami: Distributed Algorithmic Mechanism Design, Kapitel 1 und 2
(Distributed) Algorithmic Mechanism Design
2. Nisan, Ronen: Algorithmic Mechanism Design
3. Feigenbaum, Papadimitriou, Shenker: Sharing the Cost of Multicast Transmissions (Prelim. Version)
Interdomain Routing
4. Feigenbaum, Papadimitriou, Sami, Shenker: A BGP-based Mechanism for Lowest-Cost Routing
5. Hershberger, Suri: Vickery Prices and Shortest Paths: What is an edge worth? (in Proc. of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS'01)
Selfish Resource Allocation / Price of Anarchy
6. Koutsoupias, Papadimitriou: Worst-Case Equilibria und
Koutsoupias: Selfish task allocation, Survey-Artikel in Bulletin of the EATCS, Volume 81
7. Roughgarden, Tardos: How Bad is Selfish Routing?
8. Chun et al: Selfish Caching in Distributed Systems: A Game-Theoretic Analysis
Auctions
9. de Vries, Vohra: Combinatorial Auctions: A Survey
10. Chen, Deng, Sun, Yao: Dynamic Price Sequence and Incentive Compatibility
11. Lavi, Nisan: Competitive analysis of incentive compatible on-line auctions
12. Ng, Parkes, Seltzer: Virtual Worlds: Fast and Strategyproof Auctions for Dynamic Resource Allocation
Computation of Equilibria
13. McKelvey, McLennan: Computation of Equilibria in Finite Games
14. Conitzer, Sandholm: Complexity Results about Nash Equilibria
Fast alle Links verweisen auf vorläufige Versionen auf Homepages der Autoren. Diese weichen jedoch i.d.R. kaum von den veröffentlichten Versionen ab. Letztere werden in der Vorbesprechung zur Verfügung gestellt.

Kontakt

Eine Voranmeldung per Email ist möglich, aber nicht erforderlich.
Bei Fragen stehen wir gern zur Verfügung:
Jan Arpe
Hagen Völzer
Rüdiger Reischuk

Links

Wie halte ich einen guten Vortrag?

Ian Parberry's Speaker's Guide
Olivier Danvy: Issues about giving a talk, writing a report, and dealing with reviews

Links auf weitere Informationsquellen

DAS klassische Einstiegspaper: Algorithms, Games, and the Internet von Christos Papadimitriou
www.gametheory.net
Computing Nash Equilibria

Algorithmische Spieltheorie an anderen Universitäten

Berkeley: Algorithmic Aspects of Game Theory, Christos Papadimitriou, 2001
Harvard: Computational Mechanism Design, David Parkes, 2002
Hebrew Univ. Jerusalem: Foundations of Electronic Commerce, Noam Nisan, 2004
Penn: Computational Game Theory, Michael Kearns, 2003
Stanford: Multiagent Group

Software

Gambit: Software Tools for Game Theory