Dieses Forschungsprojekt fällt in den Bereich computational social choice (COMSOC), in dem die klassische Sozialwahltheorie und Ökonomie auf Theoretische Informatik (insbesondere Komplexität und Algorithmik) und Künstliche Intelligenz (insbesondere Multi-Agenten-Systeme) treffen. Das Hauptziel dieses Projekts ist es, die Berechnungskomplexität strategischen Verhaltens in zwei zentralen Gebieten der kollektiven Entscheidungsfindung zu untersuchen: Wahlen und Allokation unteilbarer Güter.
Während dies separate Themen sind, sind sie doch in verschiedener Weise miteinander verbunden und weisen gemeinsame Merkmale auf. Wir werden uns auf die kürzlich eingeführten Modelle von Online-Wahlen und „scoring allocation“ in den folgenden vier Arbeitspaketen konzentrieren:
(1) Online-Bestechung in sequenziellen Wahlen;
(2) Online-Manipulation, Online-Kontrolle und Online-Bestechung in „single-peaked“ Wahlen;
(3) Strategiesicherheit und andere Eigenschaften der scoring-basierten Allokation unteilbarer Güter und
(4) Fairness-Eigenschaften und Optimierung der sozialen Wohlfahrt bei der Allokation unteilbarer Güter.
In jedem dieser Arbeitspakete werden wir natürliche, wichtige Probleme betrachten, die jeweils eine bestimmte Art strategischen Verhaltens oder eine andere (z.B. Fairness-)Eigenschaft modellieren. Insbesondere versuchen wir zu erkunden, in welcher Weise und in welchem Ausmaß Komplexität als Schutz gegen unerwünschtes Verhalten wie z.B. Manipulationsangriffe verwendet werden kann. Unsere Komplexitätsanalyse wird Methoden der klassischen Komplexitätstheorie, der parametrisierten Komplexität und der Approximationstheorie verwenden, und außerdem werden wir empirische Studien ausführen, probabilistische Methoden anwenden und die zugrunde liegenden Wahl- und Allokationsmechanismen hinsichtlich ihrer axiomatischen Eigenschaften untersuchen.
Das Projekt wird von der Deutschen Forschungsgemeinschaft (DFG) für 3 Jahre mit rund 546.900 € gefördert.
Ansprechpartner
Prof. Dr. Jörg Rothe
Informatik
Prof. Dr. Jörg Rothe leitet seit 2000 die Arbeitsgruppe für Komplexitätstheorie und Kryptologie am Instituts für Informatik an der HHU-Düsseldorf. Seine Forschungsinteressen liegen in der Computational Social Choice, der Algorithmischen Spieltheorie und Fair Division, wobei der Fokus jeweils auf der algorithmischen und komplexitätstheoretischen Behandlung der relevanten Probleme liegt.
Im Rahmen des DIID gilt sein Interesse formalen Modellen der theoretischen Informatik für die Beschreibung und Bewertung von Nutzer-Interaktionen in Online-Partizipationsprozessen.