Lehr- und Forschungseinheit
Institut
Universität
Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik der Ludwig-Maximilians-Universität
München
Arrow's Unmöglichkeitssatz besagt, dass es kein Wahlverfahren für mehr als zwei Kandidaten geben kann, das relativ bescheidenen demokratischen Grundprinzipien genügt. Aus diesem Grund wurden zahlreiche verschiedene Verfahren entwickelt, die bestimmte, als vernünftig geltende Kriterien, erfüllen bzw. nicht erfüllen. Eines dieser Kriterien ist das Smith-Kriterium, welches besagt, dass der Gewinner einer Wahl immer in der sog. Smith Menge liegen sollte. Die Smith Menge ist die kleinste nicht-leere Menge von Kandidaten, so dass alle Kandidaten in der Menge gegenüber allen Kandidaten außerhalb der Menge von einer Mehrheit der Wähler bevorzugt werden. Es existieren verschiedene graphtheoretische Algorithmen zur Bestimmung der Smith Menge (z.B. der Algorithmus von Kosaraju zur Ermittlung starker Zusammenhangskomponenten) mit linearer worst-case Laufzeit (bzw. quadratisch in der Anzahl der Kandidaten).
Ziel dieses FoPras ist es, verschiedene effiziente Algorithmen zur Bestimmung der Smith Menge zu implementieren und experimentell zu vergleichen. Dies beinhaltet die Erzeugung von "realistischen" zufälligen Instanzen.
Dr. Felix Brandt, Zimmer 39, Oettingenstr. 67, Tel.: 089 21809406