Optimal Seat Arrangement: Structure, Algorithms, and Complexity
| Autor: | Ceylan, Esra |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: | |
| DOI: | 10.34726/hss.2023.98801 |
| Popis: | Optimal Seat Arrangement hat als Eingabe eine Menge von n Agenten, wobei jeder Agent kardinale Präferenzen gegenüber anderen Agenten hat, und einen ungerichteten Graphen mit n Knoten (Sitzgraph genannt). Die Aufgabe besteht darin, jedem Agenten einen bestimmten Knoten im Sitzgraphen zuzuordnen, um ein bestimmtes Optimalitäts- oder Fairnesskriterium, wie maximale Summe der Nutzen, maximin Nutzen, Neidfreiheit oder Austauschstabilität, zu erreichen. Bodlaender et al. [AAMAS, 2020] zeigten, dass das Erreichen jedes dieser vier Kriterien im Allgemeinen NP-schwer ist. Die Schwere hängt jedoch von einigen Sitzgraphen und Präferenzen der Agenten ab, die in realen oder alltäglichen Situationen möglicherweise nicht natürlich sind. Dies wirft die Frage auf, was Optimal Seat Arrangement NP-schwer macht. Mit dem Ziel, die Quelle der Berechnungsschwere zu identifizieren, führen wir in dieser Masterarbeit eine detaillierte klassische und parametrisierte Komplexitätsanalyse von vier Optimal Seat Arrangement Problemen, nämlich Maximum Welfare Arrangement, Maximin Utility Arrangement, Envy-Free Arrangement und Exchange-Stable Arrangement, durch. Wir betrachten natürliche Graphenklassen für den Sitzgraphen (zum Beispiel Clique-, Pfad-, Kreis-, Stern- oder Matching-Graphen), verschiedene Präferenzstrukturen (zum Beispiel binäre, nichtnegative, symmetrische oder strikte Präferenzen) und problemspezifische Parameter (zum Beispiel die Anzahl an Agenten mit Präferenzen ungleich null, die Anzahl der nicht-isolierten Knoten im Sitzgraphen oder die Knotenüberdeckungszahl des Sitzgraphen). Wir untersuchen den Einfluss dieser drei Aspekte auf die Komplexität von Optimal Seat Arrangement und geben verfeinerte algorithmische Komplexitätsschranken an. Auf diese Weise können wir klare Grenzen zwischen leichten und schweren Fällen ziehen.Wir erweitern und vervollständigen nicht nur das Wissen über die vier Optimal Seat Arrangement Probleme, sondern zeigen auch die Komplexitätsvielfalt dieser Probleme auf. Die Ergebnisse dieser Arbeit beinhalten unter anderem, dass alle betrachteten Probleme NP-schwer sind, selbst wenn jeder Agent nur eine begrenzte Anzahl an Präferenzen ungleich null hat. Diese NP-Schwere gilt sogar für einige sehr eingeschränkte Sitzgraphen und Präferenzstrukturen. Bei den beiden anderen betrachteten Parametern haben Sitzgraphenklassen und Präferenzstrukturen einen positiven Einfluss auf die (parametrisierte) Komplexität der Probleme. Schließlich korrigieren wir für strikte Präferenzen und Matching-Graphen einen Fehler von Bodlaender et al. [AAMAS, 2020]: Wir beweisen, dass die Entscheidung, ob eine neidfreie Anordnung existiert, sogar für diese Restriktionen NP-schwer bleibt. Optimal Seat Arrangement has as input a set of n agents, where each agent has cardinal preferences over other agents, and an n-vertex undirected graph (called the seat graph). The task is to assign each agent to a distinct vertex in the seat graph to achieve a certain optimality or fairness criterion such as maximum sum of utilities, maximin utility, envy-freeness, or exchange stability. Bodlaender et al. [AAMAS, 2020] showed that achieving any of these four criteria is NP-hard in general. However, the hardness relies on some seat graphs and agents’ preferences which may not be natural in real-world situations. This gives rise to the question of what makes Optimal Seat Arrangement NP-hard. Aiming to identify the source of NP-hardness, we perform in this thesis a fine-grained computational and parameterized complexity analysis of four Optimal Seat Arrangement problems, namely Maximum Welfare Arrangement, Maximin Utility Arrangement, Envy-Free Arrangement, and Exchange-Stable Arrangement. We look into natural graph classes for the seat graph (e.g., clique-, path-, cycle-, star-, or matching-graphs), different preference structures (e.g., binary, non-negative, symmetric, or strict preferences), and problem-specific parameters (e.g., the number of agents with non-zero preferences, the number of non-isolated vertices in the seat graph, or the vertex cover number of the seat graph). We investigate the influence of these three aspects on the complexity of Optimal Seat Arrangement and give more refined algorithmic complexity bounds. In this way, we identify clear borders between easy and hard cases. Not only do we extend and improve existing knowledge about the four Optimal Seat Arrangement problems but also show the diversity in complexity of these problems. The results of this thesis include that all considered problems are NP-hard even if each agent has only a bounded number of non-zero preferences. Hardness holds even for several quite restricted seat graph classes and preference structures. For the other considered parameters, the seat graph classes and preference structures have a positive impact on the (parameterized) complexity of these problems. Finally, for strict preferences and matching-graphs, we correct an error by Bodlaender et al. [AAMAS, 2020] and prove that achieving an envy-free arrangement remains NP-hard in this case. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|