Kann ein Computer alles berechnen?

Dagstuhl · Sind gesellschaftliche Entscheidungen durch Computer berechenbar? Díese und andere Fragen stellten sich Informatiker während eines sechstägigen Symposions auf Schloss Dagstuhl.

Regelmäßig Treffpunkt internationaler Wissenschaftlier: das Informatikzentrum Schloss Dagstuhl. Fotos: Informatikzentrum

Techniken aus der Sozialwahltheorie werden auch bei Wahlen eingesetzt. Wirtschafts-Professorin Annick Laruelle von der Universität des Baskenlandes geht der Frage nach, wie Bürger ihre Unzufriedenheit bezüglich Politikern bei Wahlen zum Ausdruck bringen können.

"Bisher hat der Bürger keine andere Möglichkeit als der Wahl fernzubleiben oder einen leeren Wahlzettel abzugeben", schildert Laruelle den bekannten Ist-Zustand. "Allerdings wird diese Art von Wahlboykott nicht berücksichtigt." Die Wirtschaftsprofessorin hat eine Methode entwickelt, bei der der Wähler eine positive oder eine negative Stimme pro Kandidat abgeben kann oder einfach eine Null.

Der Kandidat, der die höchste Differenz zwischen der Anzahl der positiven und negativen Stimmen erhält, wird gewählt. "Mit der Möglichkeit, auch seine Unzufriedenheit auszudrücken, kann eventuell die Wahlbeteiligung erhöht werden, was enorm wichtig ist. Denn letztendlich ist die Wahlbeteiligung das Herzstück der Demokratie", meint Laruelle. International führende Informatiker aus unterschiedlichen Teilbereichen sowie Wirtschafts-, Sozial- und Politikwissenschaftler kamen im Leibniz-Zentrum für Informatik im nördlichen Saarland zusammen, um den aktuellen Stand und weitergehende Anforderungen im Bereich computer-unterstützter gesellschaftlicher Entscheidungen zu diskutieren.

Dieses Forschungsgebiet (englisch: ,,computational social choice") verbindet die Informatik mit der Theorie der kollektiven Entscheidungen (auch ,,Sozialwahltheorie" genannt) und fördert den Gedankenaustausch in beide Richtungen. Ein Beispiel für ein Forschungsproblem aus der Sozialwahltheorie ist die Frage, was unter einer fairen Verteilung von Ressourcen zu verstehen ist: Muss jeder genau gleich viel bekommen, oder reicht es eventuell aus, wenn jedem ein gewisser Mindeststandard garantiert wird? Oder vielleicht, wenn niemand jemand anderen beneidet?

Möglichst faire Lösungen

Solche Theorien der kollektiven Entscheidungsfindung haben neuerdings Anwendung in der Informatik gefunden, zum Beispiel, wenn es um die faire Zuteilung von Rechenzeit an Naturwissenschaftler auf einem Supercomputer geht. Umgekehrt kommen traditionelle Methoden der Informatik in der Sozialwahltheorie zum Tragen, zum Beispiel bezüglich der Entwicklung schneller Algorithmen für komplexe Verteilungsschemata.

In dem Dagstuhl-Seminar wurden nicht nur Anwendungsgebiete behandelt sondern auch theoretische Konzepte. Generell geht es im Bereich computer-unterstützter gesellschaftlichen Entscheidungen um eine Entscheidungsfindung, wobei man an möglichst ,,fairen" Lösungen interessiert ist. Dabei ist zuerst einmal zu fragen, ob es überhaupt eine Lösung geben kann, oder zu zeigen, unter welchen Voraussetzungen eine Lösung zu finden ist. Insofern gibt es sehr viele Aspekte, die bei der Problemstellung und -lösung berücksichtigt werden müssen. Gerade die Vielfalt der unterschiedlichen Aspekte macht es notwendig, fachübergreifendes Expertenwissen zu berücksichtigen.

Theorie ist wichtig

Die Teilnehmer des Symposions waren sich abschließend einig, dass viele Forschungsfragen in der Sozialwahltheorie tatsächlich aus dem realen Leben hervorgehen und beispielsweise Anwendung in der Industrie oder auch in der Politik finden. Dabei sind theoretische Untersuchungen enorm wichtig, um reale Anwendungen zu ermöglichen und deren Qualität garantieren zu können. Umgekehrt werfen spezifische Eigenschaften und Randbedingungen konkreter Anwendungen theoretische Fragen auf, die von der Grundlagenforschung gelöst werden müssen. Um eine faire Verteilung von Ressourcen geht es beispielsweise bei der ,,Foodbank Australia", einer Hilfsorganisation in Australien, die Lebensmittel an Bedürftige verteilt. Informatik-Professor Toby Walsh aus Sydney berichtete auf Schloss Dagstuhl über von ihm entwickelte Techniken, die es der Foodbank Australia ermöglichen, effektiver zu arbeiten.

Dank Walsh seien die Hilfsanfragen jährlich um über zehn Prozent gestiegen. Denn er habe dazu beigetragen, dass gespendetes Essen möglichst gleichmäßig an verschiedene Wohltätigkeitsorganisationen verteilt wird. "Eine der wichtigsten Neuerungen ist die Möglichkeit, das Internet zu benutzen, sowohl für die Spenden als auch für die Verteilung", erläutert Walsh. "Über eine App kann das Essen gespendet werden. Zur Ermittlung optimaler Routen für die Abholung als auch für die Anlieferung nutzt die App die Routenplaner der Fahrzeuge." Ihm zufolge werde Essen praktisch den ganzen Tag über gespendet. Die Zuteilung und der Vertrieb geschehen direkt, das heißt, noch bevor bekannt ist, was noch alles gespendet wird. Nicht nur die faire Verteilung von Ressourcen ist ein Problem im Bereich computer-unterstützter gesellschaftlicher Entscheidung, sondern auch eine Art von Paarungs- oder Zuordnungsproblem (englisch: ,,matching"). Dieses Problem tritt beispielsweise bei Nierentransplantationen auf. "Weltweit gibt es viele Patienten, die auf eine Spenderniere warten. Obwohl es vielleicht einen bereitwilligen Spender gibt, kann die Transplantation dennoch unmöglich sein, wenn etwa Blutgruppe oder Gewebe nicht zusammen passen", erläutert Informatik-Professor David Manlove von der Universität Glasgow. In einem solchen Fall könne der Patient seine gespendete Niere mit der eines anderen Patienten in ähnlicher Situation tauschen, falls ein geeignetes Spender-Empfänger-Paar ausfindig gemacht werden könne.

"Oftmals ist ein Tausch auch erst dann möglich, wenn sich mehr als zwei Paare beteiligen und ein ganzer Kreis von Spender-Empfängerpaaren gebildet werden kann", schildert Manlove. "Der Spender von Paar A spendet seine Niere an den Empfänger von Paar B, die Spenderniere von Paar B passt zum Empfänger von Paar C, und der Spender dieses Paares kann seine Niere schließlich dem Empfänger von Paar A spenden."

In Großbritannien betreibt die ,,National Health Service Blood Transplant" seit Anfang 2007 ein Verteilungsschema für Lebendspender-Nierentransplantationen, das seit Juli 2008 wissenschaftliche Ergebnisse von Professor Manlove berücksichtigt. Er entwickelte ein optimiertes Verfahren zum Finden geeigneter Spender und Empfänger. "Dank dieses Verfahrens wurden seit 2008 insgesamt 427 Transplantationen erfolgreich durchgeführt. 2007 waren es nur acht Transplantationen, was zeigt, wie effektiv Techniken und Ergebnisse der Informatik im alltäglichen Leben eingesetzt werden können", sagt Manlove.

Zum Thema:

Hintergrund:Schloss Dagstuhl lädt das ganze Jahr über Wissenschaftler aus aller Welt ins nördliche Saarland ein, um über neueste Forschungsergebnisse in der Informatik zu diskutieren. Mehr als 3500 Informatiker von Hochschulen, Forschungseinrichtungen und aus der Industrie nehmen jährlich an den wissenschaftlichen Veranstaltungen in Dagstuhl teil. Seit 2005 gehört Schloss Dagstuhl zur Leibniz-Gemeinschaft, in der zur Zeit 89 führende außeruniversitäre Forschungsinstitute und wissenschaftliche Einrichtungen in Deutschland vertreten sind. Aufgrund ihrer gesamtstaatlichen Bedeutung fördern Bund und Länder die Institute der Leibniz-Gemeinschaft gemeinsam. redwww.dagstuhl.de