News

• Die Vorträge finden nur am 9. Februar statt. Der genaue Zeitplan ist unten aufgeführt.
• Sie finden nun auf dieser Webseite die Themen des Seminars mit ersten Literaturangaben, die Zuteilung der Themen zu den Betreuern sowie die Deadlines.

Organisation

Die Veranstaltung wird als Blockseminar am Ende der Vorlesungszeit durchgeführt. Die Vorträge finden am 9. Februar statt und können wahlweise auf deutsch oder englisch gehalten werden.

Deadlines

02.11.	Gliederung
30.11.	Ausarbeitung
21.12.	Endgültige Fassung
11.01.	Folien
Ende Januar	Vorträge

Schedule

Dienstag, 9. Februar
8:30	–	9:15	Simon Tenbusch	Iterated Regret Minimization
9:15	–	10:00	Matthias Lederhofer	Repeated Games and Bounded Rationality
10:00	–	10:30		Kaffeepause
10:30	–	11:15	Jakob Breier	Game Theory with Costly Computation
11:15	–	12:00	Daniel Franzen	Games with Incomplete Awareness
12:00	–	12:45	Lisa Wagner	Sequential Equilibria

Content

Es ist seit langem bekannt, dass die klassischen Lösungskonzepte der Spieltheorie (insbesondere Nash-Gleichgewichte) für viele moderne Anwendungen strategischer Spiele, gerade in der Informatik, nicht adäquat sind.

Viele Beispiele zeigen, dass Nash-Gleichgewichte nicht robust gegenüber fehlerhaftem bzw. irrationalem Verhalten einzelner Spieler sind, was vor allem bei der Modellierung verteilter Systeme eine Rolle spielt. Sie berücksichtigen weder Koalitionsbildung noch den Fall, dass den Spielern zum Berechnen einer optimalen Strategie nur beschränkte Ressourcen zur Verfügung stehen, und sind weiterhin nicht anwendbar in Fällen, in denen sich die Spieler nicht aller Aspekte des Spiels (Spielregeln, momentane Position, Zugmöglichkeiten, Auszahlungen) bewusst sind.

In diesem Seminar sollen weitergehende Lösungskonzepte untersucht werden, die bestimmte der genannten Teilaspekte berücksichtigen. Es werden dabei sowohl Spiele in strategischer Form als auch Spiele auf Graphen betrachtet.

Topics

Thema	Vortragende(r)	Betreuer(in)	Literatur
Robust Equilibria	Hieronymus Weyn	D. Fischer	[ADGH06]
Lower Bounds on Implementing Mediators	Adam Szanto	D. Fischer	[ADH08]
Iterated Regret Minimization	Simon Tenbusch	L. Kaiser	[HP09]
Repeated Games and Bounded Rationality	Matthias Lederhofer	T. Ganzow	[Kal87, PY94]
Game Theory with Costly Computation	Jakob Breier	T. Ganzow	[HP08]
Games with Incomplete Awareness	Daniel Franzen	B. Puchala	[Feinberg05, Feinberg09]
Sequential Equilibria	Lisa Wagner	R. Rabinovich	[MS06, MS09]
Trembling Hand Perfect Equilibria	Radek Paluszak	R. Rabinovich	[OR94]

Literature

[ADGH06]	I. Abraham, D. Dolev, R. Gonen, and J. Halpern. Distributed Computing Meets Game Theory: Robust Mechanisms for Rational Secret Sharing and Multiparty Computation. In PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pp. 53-62, 2006.
[ADH08]	I. Abraham, D. Dolev, and J. Halpern. Lower Bounds on Implementing Robust and Resilient Mediators. In Proceedings of the Fifth Theory of Cryptography Conference, pp. 302-319, 2008.
[Feinberg04]	Y. Feinberg. Subjective Reasoning: Games with Unawareness. 2004.
[Feinberg05]	Y. Feinberg. Games with Incomplete Awareness. 2005.
[Feinberg09]	Y. Feinberg. Games with Unawareness. 2009.
[HMS06]	A. Heifetz, M. Meier, and B. Schipper. Interactive Unawareness. Journal of Economic Theory, vol. 130, pp. 78-94, 2006.
[HP08]	J. Halpern and R. Pass. Game Theory With Costly Computation. 2008.
[HP09]	J. Halpern and R. Pass. Iterated Regret Minimization: A New Solution Concept. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), 2009.
[HR08]	J. Halpern and L. Rego. Interactive Unawareness Revisited. Games and Economic Behaviour, vol. 62, pp. 232-262, 2008.
[HT04]	J. Halpern and V. Teague. Rational Secret Sharing and Multiparty Computation. In Proceedings of the 36th ACM Symposium on Theory of Computing, pp. 623-632, 2004.
[Kal87]	E. Kalai. Bounded Rationality and Strategic Complexity in Repeated Games. Technical Report. Kellogg Graduate School of Management, Northwestern University, Evanston, 1987.
[MS06]	P. B. Miltersen and T. B. Sorensen. Computing sequential equilibria for two-player games. In SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 107–116, 2006.
[MS09]	P. B. Miltersen and T. B. Sorensen. Computing a quasi-perfect equilibrium of a two-player game. Economic Theory, to appear.
[OR94]	M. Osborne and A. Rubinstein. A course in game theory. The MIT Press, 1994.
[PY94]	C. H. Papadimitriou and M. Yannakakis. On Bounded Rationality And Computational Complexity. Technical Report. Indiana University, 1994.
[SKK06]	E. Ben-sasson, A. T. Kalai, and E. Kalai. An approach to bounded rationality. In Proceedings of NIPS 2006, pp. 145–152, 2006.
[UV02]	A. Urbano and J. Vila. Computational Complexity and Communication: Coordination in Two-Player Games. Econometria, vol. 70, pp. 1893-1927, 2002.
[UV04]	A. Urbano and J. Vila. Computationally Restricted Unmediated Talk Under Incomplete Information. Economic Theory, vol. 23, pp. 283-320, 2004.

Classification

• Informatik (B.Sc.)/Seminar Informatik
• Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
• Informatik (D)/Hauptstudium/Theoretische Informatik
• Mathematik (D)/Hauptstudium/Reine Mathematik
• Informatik (S II)
• Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Prerequisites

• Vorlesung Mathematische Logik
• für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Contact

Erich Grädel, Diana Fischer, Tobias Ganzow, Łukasz Kaiser, Bernd Puchala, Roman Rabinovich, Michael Ummels