Social Choice in a Social Context: A Multivariate Algorithmics Perspective
Final Report Abstract
Das Ziel dieses Forschungsprojektes war es, etablierte Modelle aus Computational Social Choice in Bezug auf Effekte, welche durch die soziale Nachbarschaft der Akteure (z.B. Wähler einer Gremiumswahl) verursacht werden, zu überarbeiten und zu erweitern. Solche Effekte können von kooperativer Natur sein (z.B. könnten Akteure zusammenarbeiten wenn sie sich kennen), von konkurrierender Natur sein (z.B. berücksichtigen Akteure, welche sich strategisch verhalten, Gegner, welche sich ebenfalls strategisch verhalten), oder berühren die Privatsphäre (z.B. sind Akteure nicht gewillt ihre vollständigen Präferenzen preiszugeben). Mein Vorschlag war es, den Einfluss solcher Effekte auf die Algorithmische Komplexität zu analysieren. Hierzu wurden Konzepte aus den Bereichen Algorithmischer Spieltheorie, Multivariater Algorithmik, Sozialer Netzwerke, und Wahltheorie genutzt. Bezüglich kooperativer Effekte wurde das Problem Group Activity Selection on Social Networks untersucht, bei welchem eine Menge von Akteuren einer Menge von Aktivitäten stabil zugeordnet werden soll und Akteure Präferenzen über den Aktivitäten sowie der jeweilig möglichen Anzahlen an Teilnehmern haben. Die erzielten Ergebnisse legen nahe, dass die Erweiterung des Modells durch die soziale Nachbarschaft der Akteure durchaus in der Lage ist, das Modell nicht nur realistischer sondern auch handhabbarer zu machen. Die bisher erzielten Ergebnisse stellen primär Identifikationen von vielversprechenden handhabbaren Spezialfällen dar. Um praktische Anwendbarkeit zu erreichen sollten Folgeuntersuchungen durchgeführt werden. Bezüglich konkurrierender Effekte hat sich herausgestellt, dass bereits die Untersuchung eines einfachen Ausbreitungsprozesses von ja/nein-Meinungen in sozialen Netzwerken, wo sich die Akteure an die einfache Mehrheitsmeinung ihrer Nachbarn anpassen, zu vielen interessanten und offenen Fragestellungen führt. Zwar stabilisieren sich derartige Prozesse, aber das Ergebnis hängt stark von der Reihenfolge ab, in welcher die Akteure ihre Meinungen aktualisieren. Während die Berechnung des bestmöglichen bzw. schlechtest möglichen Ergebnisses noch effizient machbar ist, stellen die Beeinflussung des Prozesses durch Bestechung, Störung des Netzwerks, oder Manipulation der Aktualisierungsreihenfolge algorithmisch nicht effizient handhabbare Probleme dar. Diese hohe Berechnungskomplexität kann zunächst als positives Ergebnis gewertet werden, da derartige Handlungen schwierig durchführbar erscheinen. Dennoch basieren die Ergebnisse auf „Worst-Case“-Analysen und sollten durch empirische Untersuchungen ergänzt werden. Bezüglich Privatsphäreneffekten wurde der Fokus vom ursprünglichen Forschungsziel auf das Finden einer „diversen Gewinnermenge“ umgelenkt, da dieses Problem überraschenderweise trotz der enormen Wichtigkeit bisher wenig Beachtung aus algorithmischer Sicht bekam. Eine solche Gewinnermenge ist eine Auswahl von Kandidaten, welche einerseits bestimmten Diversitätsbedingungen genügen und andererseits den Willen von Wählern möglichst gut repräsentiert. Die Kandidaten werden Kategorien zugeordnet und es werden z.B. untere und obere Schranken für die Häufigkeit der jeweiligen Kategorie in der Gewinnermenge definiert. So könnte bei der Auswahl der Teilnehmer eines Workshops sichergestellt werden, dass mindestens 30% der Teilnehmer des Workshops Nachwuchsforscher und mindestens 40% weiblich sind. Ein Grundlegendes Teilproblem, für welches mehrere Lösungsmöglichkeiten identifiziert wurde, ist die Struktur der Kategorien sowie die Diversitätsbedingungen einfach genug zu halten, damit nicht schon die Bestimmung einer diversen Kandidatenmenge (ohne Berücksichtigung der Wähler) berechnungsschwer ist. Unsere Arbeit stellt zahlreiche effiziente Algorithmen bereit, um diverse Gewinnermengen in realistischen Situationen zu bestimmen. Die meisten dieser Algorithmen können (und sollten) implementiert und getestet werden. Es sind umfangreiche Folgearbeiten zu erwarten. Insgesamt war dieses Forschungsprojekt sehr erfolgreich, da es einerseits zu realistischeren Modellen für wichtige Probleme im Bereich kollektiver Entscheidungsfindung beiträgt und andererseits für die damit verbundenen (generell berechnungsschweren) Probleme wichtige handhabbare Fälle identifiziert. Weiterhin konnten die Fähigkeiten des Antragstellers vor allem im Umgang mit spieltheoretischen Konzepten erweitert und für die Zukunft wichtige neue Forschungskontakte geknüpft werden.
Publications
- Manipulating opinion diffusion in social networks. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI ’17), pages 894–900. AAAI Press, 2017
R. Bredereck und E. Elkind
- Multiwinner elections with diversity constraints. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI ’18), 2018
R. Bredereck, P. Faliszewski, A. Igarashi, M. Lackner, und P. Skowron
