Algorithmic aspects of resource allocation and multiwinner voting: theory and experiments

Diese Arbeit befasst sich mit der Untersuchung von Themen des Forschungsgebiets Computational Social Choice im Lichte realer Anwendungen. Dabei trägt sie zu einem besseren Verständnis der Bereiche der fairen Zuordnung und der Mehrgewinnerwahlen bei. Für beide Konzepte schlagen wir – inspiriert von realen Anwendungen – verschiedene neue Begriffe und Erweiterungen bestehender Modelle vor. Anschließend analysieren wir die Komplexität der Beantwortung von Berechnungsfragen, die durch die eingeführten Konzepte aufgeworfen werden. Dabei fokussieren wir uns auf die parametrisierte Komplexität. Hierzu identifizieren wir verschiedene Parameter, welche natürliche Merkmale der von uns untersuchten Berechnungsprobleme beschreiben. Durch die Nutzung dieser Parameter entwickeln wir erfolgreich effiziente Algorithmen für Spezialfälle der untersuchten Probleme. Wir ergänzen unsere Analyse indem wir zeigen, welche Parameter vermutlich nicht verwendet werden können um effiziente Algorithmen zu finden. Dabei zeichnen wir ein umfassendes Bild der Berechnungskomplexität der untersuchten Probleme. Insbesondere konzentrieren wir uns auf vier Themen, die wir, gruppiert nach unseren beiden Schwerpunkten, unten vorstellen. Für alle Themen bis auf eines präsentieren wir Experimente, die auf Implementierungen der von uns neu entwickelten Algorithmen basieren.

Wir konzentrieren uns zunächst auf die faire Zuordnung unteilbarer Ressourcen. Hier betrachten wir eine Menge unteilbarer Ressourcen und eine Gruppe von Agenten. Jeder Agent gibt eine Bewertung des Nutzens jeder Ressource ab und die Aufgabe besteht darin, eine „faire“ Zuordnung der Ressourcen zu finden, wobei jede Ressource höchstens einem Agenten zugeordnet werden kann. Innerhalb dieses Bereiches konzentrieren wir uns auf die beiden folgenden Problemstellungen.

Der soziale Kontext bei der fairen Zuordnung unteilbarer Ressourcen. In vielen Szenarien, in denen Ressourcen zugeordnet werden sollen, ist es unwahrscheinlich, dass jeder Agent alle anderen kennt. Vorstellbar ist beispielsweise ein Szenario, in dem die Agenten Mitarbeiter eines großen Unternehmens repräsentieren. Es ist höchst unwahrscheinlich, dass jeder Mitarbeiter jeden anderen Mitarbeiter kennt. Motiviert durch solche Szenarien entwickeln wir ein neues Modell der graph-basierten Neidfreiheit. Wir erweitern den klassischen Neidfreiheitsbegriff um die sozialen Beziehungen von Agenten, die durch soziale Netzwerke modelliert werden. Einerseits zeigen wir, dass wenn das soziale Netzwerk der Agenten einfach ist (zum Beispiel, wenn es sich um einen gerichteten azyklischen Graph handelt), in manchen Fällen faire Zuordnungen effizient gefunden werden können. Andererseits stellen wir diesen algorithmisch positiven Ergebnissen mehrere NP-schweren Fällen entgegen. Ein Beispiel für einen solchen Fall sind soziale Netzwerke mit einem konstanten Knotengrad.

Faire Zuteilung an wenige Agenten mit begrenzter Rationalität. Begrenzte Rationalität beschreibt die Idee, dass Menschen aufgrund kognitiver Grenzen dazu neigen, Probleme, mit denen sie konfrontiert werden, zu vereinfachen. Eine mögliche Folge dieser Grenzen ist, dass menschliche Agenten in der Regel einfache Bewertungen der gewünschten Ressourcen abgeben; beispielsweise könnten Agenten die verfügbaren Ressourcen nur in zwei Gruppen, erwünschte und unerwünschte Ressourcen, kategorisieren. Durch Anwendung von Techniken zum Lösen von Ganzzahligen Linearen Programmen zeigen wir, dass unter der Annahme einer kleinen Anzahl von Agenten die Ausnutzung begrenzter Rationalität dabei hilft, effiziente Algorithmen zum Finden neidfreier und Pareto-effizienter Zuweisungen zu entwickeln. Weiterhin zeigen wir, dass unser Ergebnis ein allgemeines Verfahren liefert, welches auf eine Reihe verschiedener Fairnesskonzepte angewendet werden kann, wie zum Beispiel Neidfreiheit bis auf ein Gut oder Neidfreiheit bis auf irgendein Gut. Auf diese Weise gewinnen wir effiziente Algorithmen für eine Reihe fairer Zuordnungsprobleme (wenige Agenten mit begrenzter Rationalität vorausgesetzt). Darüber hinaus zeigen wir empirisch, dass unsere Technik in der Praxis anwendbar ist.

Weiterhin untersuchen wir Mehrgewinnerwahlen, bei denen uns eine Menge von Wählern sowie ihre Präferenzen über eine Reihe von Kandidaten gegeben sind. Das Ergebnis eines Mehrgewinnerwahlverfahrens ist eine Gruppe (oder eine Menge von Gruppen im Falle eines Unentschiedens) von Kandidaten, welche die Präferenzen der Wähler am besten einem bestimmten Ziel folgend widerspiegeln. In diesem Kontext untersuchen wir die folgenden Themen.

Die Robustheit von Wahlergebnissen. Wir untersuchen, wie robust die Ergebnisse von Mehrgewinnerwahlen gegenüber möglicher Fehler der Wähler sind. Unter der Annahme, dass jeder Wähler eine Stimme in Form einer Rangliste von Kandidaten abgibt, modellieren wir einen Fehler als einen Tausch benachbarter Kandidaten in der Rangliste. Wir zeigen, dass für Wahlregeln wie SNTV, k-Approval und k-Borda die minimale Anzahl an Vertauschungen, welche zu einer Ergebnisänderung führt, einfach zu berechnen ist. Für STV und die Chamberlin-Courant-Regel ist diese Aufgabe allerdings NP-schwer. Wir schließen unsere Untersuchung der Robustheit unterschiedlicher Wahlregeln ab mit einer experimentellen Evaluierung der durchschnittlichen Anzahl zufälliger Vertauschungen, die zu einer Änderung des Ergebnisses führen.

Strategische Abstimmung bei Wahlen mit mehreren Gewinnern. Wir fragen, ob eine bestimmte Gruppe von kooperierenden Wählern ein Wahlergebnis zu ihren Gunsten manipulieren kann. Dabei konzentrieren wir uns auf die k-Approval-Wahlregel. Wir zeigen, dass die Berechnungskomplexität der besagten Manipulation eine reiche Struktur besitzt. Auf der einen Seite identifizieren wir mehrere Fälle in denen das Problem in Polynomzeit lösbar ist. Auf der anderen Seite identifizieren wir jedoch auch NP-schwere Fälle. Für einige von ihnen zeigen wir, wie die Berechnungsschwere durch parametrisierte Algorithmen umgangen werden kann. Wir präsentieren zudem experimentelle Untersuchungen, welche darauf hindeuten, dass unsere Algorithmen in der Praxis anwendbar sind.