Seminar Algorithmische Spieltheorie (MuA)

(Prof. Dr. Burkhard Monien, Wintersemester 2007/08)

Allgemeine Informationen

Ablauf:
- Zur Anmeldung zum Seminar muss das verlinkte Anmeldeformular bis zum 21.01.2008 ausgefüllt und unterschrieben im Sekretariat eingegangen sein. Eine eventuell spätere Abmeldung kann mit dem verlinkten Abmeldeformular bis einschließlich 24.01.2008 (Eingang im Sektariat) erfolgen.
- Die Seminarvorträge finden im Rahmen einer Blockveranstaltung am 31.01.2008 statt.
- Die Vortragsdauer beträgt jeweils 45 Minuten. Im Anschluss an jeden Vortrag sind 10 Minuten für Fragen und Diskussion vorgesehen.
- Im Rahmen des Seminars ist eine Seminarausarbeitung anzufertigen.
- Das Seminar beinhaltet ferner ein separates 30-minütiges Fachgespräch über drei vom Seminarteilnehmer wählbare Themen.
Alle an uns elektronisch gesendete Dokumente bitte ausschließlich in einem der folgenden Formate:
- LaTeX-Quelltext
- PDF
- PostScript
Hinweise zum Erstellen von Seminarausarbeitungen und Halten von Seminarvorträgen:
- Rahmenrichtlinien für Seminare
- Seminare: Hinweise für Vortrag und Ausarbeitung
- Ratschläge zum Abfassen eines schlechten Referats
- Jede Ausarbeitung enthält ein Literaturverzeichnis, das mindestens die Literatur umfasst, die in der Ausarbeitung verwendet wird. Denken Sie daran, dass Artikel aus Konferenzbänden und Zeitschriften immer mit Seitennummern angegeben werden.
- Daumenregel: Beweise werden in der Seminarausarbeitung üblicherweise länger und ausführlicher als in Konferenzveröffentlichungen, Zwischentexte können manchmal kürzer ausfallen. Es muss die eigene Leistung erkennbar werden. Insbesondere werden daher reine Übersetzungsarbeiten nicht akzeptiert.
- Halten Sie im eigenen Interesse frühzeitig Rücksprache mit Ihrem Betreuer. Fühlen Sie sich ferner jederzeit ermuntert und aufgefordert, Ihren Betreuer bei Fragen anzuschreiben oder persönlich bei ihm (am besten nach Absprache) vorbeizukommen.

Zeitplan

Mittwoch, den 17.10.2007, um 12:15 Uhr: Vorbesprechung zum Seminar im Raum F0.530.
Montag, den 21.01.2008, um 9:00 Uhr: Abgabe der vorläufigen Seminarausarbeitungen.
Bemerkung: Aus der vorläufigen Seminarausarbeitung sollte erkenntlich werden, dass die wesentlichen Ideen des zu bearbeitenden Papiers vollständig verstanden wurden und präsentiert werden können.
Mittwoch, den 23.01.2008: Rückmeldung vom Betreuer. Bei Bedarf wird eine persönliche Besprechung mit dem Betreuer in den folgenden Tagen vereinbart.

Donnerstag, den 31.01.2008: Seminar als Blockveranstaltung im Raum F2.419 mit folgendem Ablauf.

1. Teil
Lokale Suche, von 10:30 Uhr (s.t.) bis 12:25 Uhr:

Uhrzeit	Seminarteilnehmer	Autoren des Papiers	Titel
10:30 – 11:25	Andreas Kumlehn	David S. Johnson, Christos H. Papadimtriou, Mihalis Yannakakis	How Easy is Local Search?
11:30 – 12:25	Sebastian Kniesburges	Alex Fabrikant, Christos Papadimitriou, Kunal Talwar	The Complexity of Pure Nash Equilibria

2. Teil:
Mechanism Design, von 14:00 Uhr (s.t.) bis 14:55 Uhr:

Uhrzeit	Seminarteilnehmer	Autoren des Papiers	Titel
14:00 – 14:55	Christoph Werner	Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker	Sharing the Cost of Multicast Transmissions

Freitag, den 29.02.2008, um 9:00 Uhr: Abgabe der endgültigen Seminarausarbeitungen.
März 2008: Vorgeschlagener Zeitraum für die Fachgespräche.

Liste der Themen

Die jeweiligen Seminar-Teilnehmer sind in fettem Schriftstil dargestellt. Nicht vergebene Papiere erscheinen in grau.

Aus dem Bereich der lokalen Suche (betreut von Dominic Dumrauf)
- Andreas Kumlehn: David S. Johnson, Christos H. Papadimtriou, Mihalis Yannakakis; "How Easy is Local Search?"; Journal of Computer and System Science, Vol. 37, No.1, 1988
- Mark W. Krentel; "On Finding and Verifying Locally Optimal Solutions"; SIAM Journal on Computing, Vol. 19, No.4, 1990
- Sebastian Kniesburges: Alex Fabrikant, Christos Papadimitriou, Kunal Talwar; "The Complexity of Pure Nash Equilibria"; STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing
- James B. Orlin, Abraham P. Punnen, Andreas S. Schulz; "Approximate local search in combinatorial optimization"; SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms
- Heiner Ackermann, Heiko Röglin, Berthold Vöcking; "On the Impact of Combinatorial Structure on Congestion Games"; FOCS '06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
- S. Chien and A. Sinclair; "Convergence to approximate Nash equilibria in congestion games"; Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
- Svatopluk Poljak; "Integer Linear Programs and Local Search for Max-Cut"; SIAM Journal on Computing, Vol. 24, No.4, 1995
- Philippe Chapdelaine and Nadia Creignou; "The Complexity of Boolean Constraint Satisfaction Local Search Problems"; Annals of Mathematics and Artificial Intelligence, Vol. 43, No. 1-4, 2005
Aus dem Bereich Mechanism Design (betreut von Florian Schoppmann)
- Noam Nisan and Amir Ronen, "Algorithmic Mechanism Design"; Games and Economic Behavior, Vol. 35, No. 1–2, 1999
  DOI: 10.1006/game.1999.0790
- Hervé Moulin and Scott Shenker; "Strategyproof sharing of submodular costs: budget balance versus efficiency"; Economic Theory, Vol. 18, No. 3, 2001
  Online verfügbar über SpringerLink
- Kamal Jain and Vijay Vazirani; "Applications of approximation algorithms to cooperative games"; Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC 2001)
  DOI: 10.1145/380752.380825
- Christoph Werner: Joan Feigenbaum, Christos H. Papadimitriou, and Scott Shenker; "Sharing the Cost of Multicast Transmissions"; Journal of Computer and System Sciences, Vol. 63, No. 1, 2001
  DOI: 10.1006/jcss.2001.1754
- Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano and Carmine Ventre; "New Constructions of Mechanisms with Verification"; Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006)
  DOI: 10.1007/11786986_52
- Tim Roughgarden and Mukund Sundararajan; "New trade-offs in cost-sharing mechanisms"; Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006)
  DOI: 10.1145/1132516.1132528
- Janina Brenner and Guido Schäfer; "Cost Sharing Methods for Makespan and Completion Time Scheduling"; 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2007)
  DOI: 10.1007/978-3-540-70918-3_57
- Aranyak Mehta, Tim Roughgarden, and Mukund Sundararajan; "Beyond moulin mechanisms"; Proceedings of the 8th ACM Conference on Electronic Commerce (EC 2007)
  DOI: 10.1145/1250910.1250912

Letzte Änderung: 28. Jan. 2008 - Dominic Dumrauf, Florian Schoppmann

Weiter zum Anfang