Gerechte Zuordnungen: Kollektive Entscheidungsprobleme aus der Perspektive von Mathematik und theoretischer Informatik

Abstract

Wir untersuchen verschiedene Fragestellungen der Sozialwahltheorie aus Sicht der Computational Social Choice. Für ein Problem, das in Bezug zu einem Kollektiv von Agenten steht (z.B. Aufteilungen von Ressourcen oder Repräsentantenwahlen), stehen verschiedene Alternativen als Lösung zur Verfügung; ein wesentlicher Aspekt sind dabei die diversen Pr\"aferenzen der Agenten gegenüber den Alternativen. Die Qualität der Lösungen wird anhand von Kriterien aus den Sozialwissenschaften (Fairness), der Spieltheorie (Stabilität) und den Wirtschaftswissenschaften (Effizienz) charakterisiert. In Computational Social Choice werden solche Fragestellungen mit Werkzeugen der Mathematik (z.B. Logik und Kombinatorik) und Informatik (z.B. Komplexitätstheorie und Algorithmik) behandelt. Als roter Faden zieht sich die Frage nach sogenannten "`gerechten Zuordnungen"' durch die Dissertation.

Für die Zuordnung von Gütern zu Agenten zeigen wir, wie mithilfe eines dezentralisierten Ansatzes Zuordnungen gefunden werden können, die Ungleichheit minimieren. Wir analysieren das Verhalten dieses Ansatzes für Worst-Case-Instanzen und benutzen dabei eine innovative Beweismethode, die auf impliziten rekursiven Konstruktionen unter Verwendung von Argumenten der Infinitesimalrechnung beruht.

Bei der Zuordnung von Agenten zu Aktivitäten betrachten wir das vereinfachte Szenario, in dem die Agenten Präferenzen bezüglich der Aktivitäten haben und die Menge der zulässigen Zuordnungen Beschränkungen bezüglich der Teilnehmerzahlen pro Aktivität unterliegt. Wir führen verschiedene Lösungskonzepte ein und erläutern die Zusammenhänge und Unterschiede dieser Konzepte. Die zugehörigen Entscheidungsprobleme zur Existenz und Maximalität entsprechender Zuordnungen unterziehen wir einer ausführlichen Komplexitätsanalyse.

Zuordnungsprobleme können auch als Auktionen aufgefasst werden. Wir betrachten ein Szenario, in dem die Agenten Gebote auf Transformationen von Gütermengen abgeben. In unserem Modell sind diese durch die Existenz von Gütern charakterisiert, die durch die Transformationen nicht verbraucht werden. Von Interesse sind die Kombinationen von Transformationen, die den Gesamtnutzen maximieren. Wir legen eine (parametrisierte) Komplexitätsanalyse dieses Modells vor.

Etwas abseits der Grundfragestellung liegen unsere Untersuchungen zu kombinierten Wettkämpfen. Diese interpretieren wir als Wahlproblem, d.h. als Aggregation von Ordnungen. Wir untersuchen die Anfälligkeit für Manipulationen durch die Athleten.

We investigate questions from social choice theory from the viewpoint of computational social choice.

We consider the setting that a group of agents faces a collective decision problem (e.g., resource allocation or the choice of a representative): they have to choose among various alternatives. A crucial aspect are the agents' individual preferences over these alternatives.

The quality of the solutions is measured by various criteria from the fields of social sciences (fairness), game theory (stability) and economics (efficiency). In computational social choice, such problems are analyzed and accessed via methods of mathematics (e.g., logic and combinatoric) and theoretical computer science (e.g. complexity theory and algorithms). The question of so called `fair assignments' runs like a common thread through most parts of this dissertation.

Regarding allocations of goods to agents, we show how to achieve allocations with minimal inequality by means of a distributed approach. We analyze the behavior of this approach for worst case instances; therefor we use an innovative proof technique which relies on implicit recursive constructions and insights from basic calculus.

For assignments of agents to activities, we consider a simplified scenario where the agents express preferences over activities and the set of feasible assignments is restricted by the number of agents which can participate in a (specific) activity. We introduce several solution concepts and elucidate the connections and differences between these concepts. Furthermore, we provide an elaborated complexity analysis of the associated decision problems addressing existence and maximality of the corresponding solution concepts.

Assignment problems can also be seen as auctions. We consider a scenario where the agents bid on transformations of goods. In our model, each transformation requires the existence of a `tool good' which is not consumed by the transformation. We are interested in combinations of transformations which maximize the total utility. We study the computational complexity of this model in great detail, using methods from both classical and parameterized complexity theory.

Slightly off topic are our investigations on combined competitions. We interpret these as a voting problem, i.e., as the aggregation of orders. We investigate the susceptibility of these competitions to manipulation by the athletes.