Algorithmische Aspekte dynamischer Präferenzbestimmung und –aggregation (Präferenzaggregation)

Teilprojektleiter: Prof. Dr. Jörg Rothe

Erkenntnisinteresse und Fragestellung

Im Rahmen der internetvermittelten kooperativen Normsetzung sind häufig Situationen zu erwarten, bei denen Individuen („Wähler“) aus verschiedenen Alternativen („Vorschlägen für Normen“) diejenigen auswählen müssen, die ihren Präferenzen am besten entsprechen.  Die Aggregation von Präferenzen bei der internetvermittelten kooperativen Normsetzung ist nicht machbar, ohne dabei die folgenden Besonderheiten gegenüber üblichen Wahlen als leitende Fragestellungen zu berücksichtigen:

  • Statt jederzeit von allen Beteiligten vollständige Präferenzen über sämtliche Alternativen zu erwarten, sollte man von nur partieller Information ausgehen.  Wie lassen sich Abstimmungen für solche partiellen Präferenzen und die entsprechenden Probleme der manipulativen Beeinflussung modellieren und algorithmisch analysieren?
  • Anders als bei simultanen Wahlen ist die Präferenzbildung und –aggregation hier sequenziell: Wähler stimmen oft in zeitlicher Reihenfolge ab, Vorschläge für Normen entstehen nacheinander und die Präferenzen der Wähler über diese Vorschläge können sich mit der Zeit ändern. Wie modelliert man diesen dynamischen Prozess? Wie erreicht man, dass sich im zeitlichen Verlauf Vorschläge in eine von der Mehrheit gewünschte Richtung bewegen, bis ein Konsens erreicht bzw. eine Entscheidung getroffen werden kann? Wie kann man manipulative Einflussnahme bzw. strategische Verfälschung der Ergebnisse nach Möglichkeit verhindern, nicht nur bei Abstimmungen, sondern auch bei der judgment aggregation und der Evaluierung von Argumenten in der Gruppenargumentation?
  • Im Gegensatz zu Alternativen, über die in der klassischen Wahltheorie abgestimmt wird, sind Normen kompliziertere Gebilde: Mehrere Normen können von denselben Variablen bzw. Attributen abhängen. Wie kann man kollektiv bevorzugte Normen dadurch ermitteln, dass direkt über die zugrunde liegenden Variablen bzw. Attribute abgestimmt wird?

Der Fokus dieses problemspezifischen Teilprojekts liegt im Bereich Theoriebildung und leistet Grundlagenforschung. Insbesondere wird es wesentlich zur Entwicklung des bereits im Forschungsprogramm (Abschnitt 1.4) erwähnten Moduls für Abstimmungen beitragen. Unterstützt durch empirische Analysen (etwa durch experimentelle Untersuchungen der Manipulationsprobleme für „typische“ Eingaben) werden die gewonnenen theoretischen Erkenntnisse zentral für die Systementwicklung (also den Entwurf von Systemkomponenten) sein und im Praxiseinsatz erprobt.

Forschungsansatz und geplantes Vorgehen

Die Mechanismen zur Präferenzbestimmung und –aggregation sollen in einem zeitabhängigen dynamischen Modell entwickelt und analysiert werden. In diesem Modell sollen für sequenzielle Wahlen mit partieller Information verschiedene Probleme der Manipulation, Wahlkontrolle und –bestechung im Sinne von „Online-Algorithmen“ (Borodin & El-Yaniv 1998) untersucht werden. Solche Algorithmen verarbeiten ihre Eingabe Stück für Stück seriell in der Reihenfolge, in der die Daten eingegeben werden; sie rechnen also schon, bevor die Eingabedaten vollständig vorliegen. Nach unserem Kenntnisstand sind Online-Algorithmen bisher nicht auf Wahlprobleme angewandt worden. In unserem Modell kennt der aktuelle Manipulator die bisher abgegebenen Stimmen, aber nicht die künftigen, und muss „online“ entscheiden, mit welcher strategischen Stimme er seinen Erfolg maximieren kann, egal wie die künftigen Wähler abstimmen.  Dies ist ein für Online-Algorithmen typischer „Maxi-min“-Ansatz, mit dem Manipulation, Kontrolle und Bestechung sowohl für Wahlen als auch in der judgment aggregation und bei Modellen der Gruppenargumentation im Sinne von Caminada et al. (2011) algorithmisch und komplexitätstheoretisch untersucht werden sollen. Ein ähnlicher Zugang wurde von Walsh (2011) in einem anderen Gebiet – Cake-cutting-Algorithmen – gewählt.

Innerhalb des Gesamtprojekts wird unser Teilprojekt dazu mit dem Teilprojekt Technik zusammenarbeiten, denn unsere theoretischen Erkenntnisse sollen den Entwurf von Systemkomponenten – speziell der zu implementierenden Aggregations- und Kooperationsmechanismen – leiten, um Resistenz gegen Manipulation sowie die Authentizität von Benutzeraktionen zum Schutz vor Betrügern (Stichwort: „false-name manipulation“ (Conitzer & Yokoo 2010)) sicherzustellen. Insbesondere soll so ein Modul für Abstimmungen entwickelt werden, wie es im Forschungsprogramm (Abschnitt 1.4) beschrieben wurde.

Ein besonderer Wert dieses Teilprojekts liegt darin, dass es einen theoretischen Informatikbeitrag zur Computational Social Choice leistet und somit eine Brücke von den theoretischen sozialwissenschaftlichen Themen des Gesamtprojekts – wie z.B. dem Teilprojekt Design – zur technischen und praktischen Informatik – wie den Teilprojekten Technik und Modellierung –  schlägt. So können die im Teilprojekt Modellierung entwickelten Formalisierungsmethoden und Werkzeuge eingesetzt werden, um die in unserem Teilprojekt relevanten Modelle der Online-Manipulation zu untersuchen.

Der Aspekt der partiellen Information (Wähler mit partiellen Präferenzen) bei der internetvermittelten kooperativen Normsetzung wird durch dasPossible-Winner“-Problem (Konczak & Lang 2005) modelliert, das das Manipulationsproblem verallgemeinert. Dieser Begriff soll hier ebenfalls in einem dynamischen Modell untersucht werden.

Der Aspekt, dass Normen –  anders als gewöhnliche Alternativen –  eine kombinatorische Struktur aufweisen und von mehreren Attributen abhängen können, über die die Wähler direkt abstimmen können, wird durch Wahlen in „combinatorial domains“ ausgedrückt (Chevaleyre et al. 2008, Lacy & Niou 2000, Lang & Xia 2009). Da solche kombinatorischen Präferenzstrukturen eine exponentielle Größe in der Zahl der Attribute haben können, müssen sie kompakt repräsentiert werden.  Eine Möglichkeit, dies zu erreichen, sind conditional preference networks (CP-nets). Auch hier bietet sich eine Zusammenarbeit mit dem Teilprojekt Modellierung an und ebenso mit dem Kooperationspartner Ulle Endriss (University of Amsterdam), der ein ausgewiesener Experte für Präferenzaggregation in combinatorial domains ist (Chevaleyre et al. 2008). In Zusammenarbeit mit dem Teilprojekt Komplexitätsreduktion sollen dabei die in der Praxis verwendeten Mechanismen der Komplexitätsreduktion unter theoretischen – und vor allem auch algorithmischen – Aspekten untersucht werden, inbesondere auch im Hinblick auf die manipulative Einflussnahme im Zuge der Komplexitätsreduktion.