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