Vorlesung "Computational Social Choice"
angeboten im WS 2007/2008
an der Lehr- und Forschungseinheit 5 (Theoretische Informatik)
des Instituts für Informatik der Universität München
Vorlesung
Dr. Felix Brandt, 2-stündig
Zeit und Ort: Mittwoch, 10.15-11.45 Uhr,
Oettingenstr. 67, Oe 0.41
Beginn: 17.10.2007
Inhalt
"Social Choice Theory" beschäftigt sich mit Methoden zur kollektiven Entscheidungsfindung. Neben den klassischen Anwendungen wie Wahlverfahren, haben diese Methoden in den letzten Jahren Anwendung in verschiedenen Teilgebieten der Informatik wie beispielsweise der künstlichen Intelligenz oder der Bewertung von Webseiten für Suchmaschinen gefunden. Der Schwerpunkt dieser Vorlesung liegt auf der Analyse und dem Vergleich von bekannten Verfahren wie denen von Lewis Carroll, John Kemeny oder Google's PageRank-Algorithmus. Insbesondere werden dabei algorithmische Aspekte dieser Verfahren betrachtet.
Anforderungen
Teilnahmevorraussetzungen:
- bestandenes Vordiplom in Informatik oder Mathematik
- Interesse an (mathematisch) formaler Modellierung und Analyse interessanter Probleme
- Grundwissen in Graphentheorie, Algorithmik und Komplexitätstheorie ist nützlich, aber nicht notwendig
Kriterium zur Erlangung eines Scheins:
- Bei Bedarf wird ein Vorlesungsschein nach einer erfolgreichen mündlichen Prüfung ausgestellt.
Vorläufige Themenübersicht
- Einführung, P und NP, Wahlverfahren [pdf]
- Präferenzen, Satz von May, Satz von Moulin [pdf]
- Punkteverfahren und Condorcet-Verfahren [pdf]
- Fishburns Klassifikation von Condorcet-Verfahren
- Satz von McGarvey
- Social Choice Correspondences
- Copeland
- Good und Schwartz [pdf]
- Von Neumann-Morgenstern stabile Mengen [pdf]
- Slater und Banks [pdf]
- Voting Trees (Paul Harrenstein) [pdf]
- Uncovered set und Minimal Covering set [pdf]
- Social Welfare Functions
- Arrows Unmöglichkeitssatz
- Dodgson (Lewis Carroll) und Kemeny-Young [pdf]
- Ranking Systems und PageRank
Literatur
Da es sich um ein sehr aktuelles Forschungsgebiet handelt, ist (noch) kein Lehrbuch verfügbar. Die Vorlesungsfolien werden jede Woche auf dieser Webseite veröffentlicht.
Einführend (online):
- Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet. A Short Introduction to Computational Social Choice. In Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM-2007), LNCS 4362, Springer-Verlag, 2007.
- U. Endriss and J. Lang (eds.). Proceedings of the 1st International Workshop on Computational Social Choice, ILLC, 2006.
- P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. A Richer Understanding of the Complexity of Election Systems. In "Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz" (S. Ravi and S. Shukla, eds.), Springer-Verlag, 2007.
Weiterführend:
- M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
- J. Laslier. Tournament Solutions and Majority Voting. Springer-Verlag, 1997.
- H. Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, 1988.
Links
- Forum zum Bereich „Theoretische Informatik” bei die-informatiker.net