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
- Bachelorstudiengang Informatik, 5. Semester
- 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
- - kurze schriftliche Zusammenfassung der vorgestellten Arbeit
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 - ... | |
| 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
- 7. Roughgarden, Tardos: How Bad is Selfish Routing?
- 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
- 10. Chen, Deng, Sun, Yao: Dynamic Price Sequence and Incentive Compatibility
- Computation of Equilibria
- 13. McKelvey, McLennan: Computation of Equilibria in Finite Games
- 14. Conitzer, Sandholm: Complexity Results about Nash Equilibria
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
- Harvard: Computational Mechanism Design, David Parkes, 2002