Parametrisierte Komplexität der gemeinsamen Urteilsfindung

Im Forschungsgebiet computer-unterstützter gesellschaftlicher Entscheidungen (englisch: Computational Social Choice, kurz ComSoc) werden Konzepte der (theoretischen) Informatik angewandt, um Methoden zur kollektiven Entscheidungsfindung aus individuellen Präferenzen oder Urteilen zu untersuchen. Ein Teilbereich von ComSoc beschäftigt sich mit der gemeinsamen Urteilsfindung (englisch: Judgment Aggregation), d.h. mit Techniken, mittels derer Akteure ihre individuellen Meinungen zu einem gemeinsamen Urteil verbinden können. Ein wichtiger Aspekt bei der Untersuchung solcher sogenannter Judgment-Aggregation-Prozeduren ist die Berechnungskomplexität von in ihrem Zusammenhang autretenden Problemen, also die Zeit, die benötigt wird, um diese Probleme algorithmisch zu lösen. So sind beispielsweise Judgment- Aggregation-Prozeduren von Interesse, die ein effizientes Berechnen eines gemeinsamen Urteils erlauben. Das Forschungsprojekt Parametrisierte Komplexität der gemeinsamen Urteilsfindung untersucht die Berechnungskomplexität verschiedener im Bereich der gemeinsamen Urteilsfindung auftretender Probleme mit Methoden der parametrisierten Komplexitätstheorie. Diese Methoden ermöglichen ein äußert detailliertes Bild der Berechnungskomplexität dieser Probleme, da mehrere Eingabeparameter miteinbezogen werden können. Die avisierten Ergebnisse bieten eine präzisere Sicht auf die Bedingungen, unter denen Probleme der gemeinsamen Urteilsfindung effizient gelöst werden können, und auf die Bedingungen, unter denen dies nicht möglich ist. Dieses Projekt initiiert die strukturelle parametrisierte Komplexitätsanalyse von im Bereich der gemeinsamen Urteilsfindung auftretenden Problemen. Die Durchführung dieses Forschungsprojekts erfordert die Weiterentwicklung relevanter Methoden der parametrisierten Komplexitätstheorie, da deren Standardinstrumentarium nicht ausreicht, um zahlreiche Probleme aus dem Bereich der gemeinsamen Urteilsfindung adäquat zu analysieren. Wir werden neueste Konzepte der parametrisierten Komplexitättheorie, die geeignet sind, diese Lücke zu schließen, weiterentwickeln, um eine bessere Analyse zu ermöglichen. Die daraus resultierenden Methoden können in Zukunft dazu verwendet werden, Probleme in anderen Bereichen der Informatik zu untersuchen.

Das mathematische Modell von "Judgment Aggregation" kann benützt werden um komplexe Wahlszenarien zu modellieren und auszuführen. Im Allgemeinen, führt dies zu rechentechnisch teure Aufgaben. Das heißt, dass es Jahrhunderte dauern kann um den Gewinner von einem Wahlszenario zu berechnen. Die wichtigsten Beiträge dieses Projektes bestehen aus dem Identifizieren von bestimmten Fällen, in denen wir auf leistungsfähiger Art mit komplexen Wahlszenarien umgehen können, mithilfe von dem Modell der "Judgment Aggregation". Ein anschauliches Beispiel von einem komplexen Wahlszenario, ist das Szenario von "Participatory Budgeting". In diesem Szenario gibt es ein Budget um eine Kombination von Projekten zu finanzieren. Auch gibt es Wähler, die ihre Meinung geben, welche Projekte finanziert werden sollen von dem Budget. Dies ist ein komplexes Wahlszenario: wenn man einfach die Wahlregel der Mehrheit benützt, kann es sein das man über das Budget hinausgeht. Das Szenario von "Participatory Budgeting" ist ein realistisches Szenario, das schon auf verschiedene Orten auf der Welt benützt wird, sowie in New York und Chicago, zum Beispiel. Das Modell von "Judgment Aggregation" bietet mehrere Wahlregeln die in diesem Szenario benützt werden können. Ein Beispiel von so einer Regel is die Regel die die Kombination von Projekten selektiert, die gesamte Zufriedenheit unter Wählern maximiert, und gleichzeitig nicht über das Budget hinausgeht. Ein der wichtigsten Ergebnisse dieses Projektes ist ein Verfahren, das eine effiziente Anwendung dieser Wahlregel ermöglicht in dem Szenario von "Participatory Budgeting". Dieses Verfahren basiert auf eine intelligente Verwendung von verschiedenen mathematischen Werkzeugen aus dem Bereich der theoretischen Informatik. Die Ergebnisse dieses Projektes enthalten auch leistungsfähige Verfahren für andere raffinierten Wahlregeln für das Szenario von "Participatory Budgeting", sowie für andere komplexen Wahlszenarien. Das Forschungsprojekt hat auch die Grenzen dieser Verfahren untersucht. Die Ergebnisse dieses Projektes enthalten auch komplementäre Ergebnisse, die zeigen, in welchen Fällen zusätzliche Einschränkungen notwendig sind um leistungsfähigen Verfahren zu ermöglichen. Solche Ergebnisse sind unumgänglich für die Entwicklung von effizienten Verfahren für komplexe Wahlszenarien. Einerseits konstituieren die Ergebnisse dieses Projektes einen nützlichen weiteren Schritt in der Suche nach theoretischem Verständnis der rechentechnischen Eigenschaften von komplexen Wahlszenarien. Außerdem zeigen die Ergebnisse auf nützliche und interessante Richtungen für zukünftige theoretischen Forschung. Anderseits liefern die Ergebnisse konkrete Verfahren, die benützt werden können um Software zu entwickeln, mit der wir komplexe Wahlszenarien auf angemessener Art behandeln können. Solche Software würde die gesellschaftliche Relevanz der theoretischen Forschung dieses Projektes verkörpern.