Loading…
Application-oriented collective decision making: experimental toolbox and dynamic environments
Böhmer, Niclas
Foundations of Computing
Collective decision making problems capture situations where the preferences of agents need to be aggregated into a compromise solution. This thesis focuses on two such problems: voting, where "voters" express preferences over "candidates" and a "winning" candidate needs to be identified, and stable matching, where "agents" have preferences over each other and a "stable" matching of the agents needs to be found.
The overarching goal of this thesis is to promote and empower application-oriented theoretical and experimental research on collective decision making problems. Contributing to this goal, in Parts I and II, we extend the toolbox for computational experiments. Such experiments could for instance be used to evaluate the running time of an algorithm, the similarity between two mechanisms, or the quality of a heuristic, and can thus complement, check, and guide theoretical research with practical insights. Concretely, in Chapter 2, after formulating challenges one faces when conducting such experiments, we introduce a map of elections for planning and evaluating experiments. Next, in Chapter 3, we present a large collection of multi-source real-world preference data, which we subsequently classify, analyze, and use to address some classic questions from social choice. In Chapter 4, we turn to synthetic data sources and take a closer look at the popular Mallows model. In the first part of that chapter, we challenge classic ways of using the Mallows model and provide a new parameterization that behaves in line with real-world evidence. In the second part, we propose a new method for "preference learning", and demonstrate how to use it to fit (mixtures of) Mallows models to our previously collected data to obtain a better understanding of it. Subsequently, in Chapter 5, we construct a map of stable matching instances to visualize the relation between instances and experimental results. This involves the introduction and analysis of a distance measure and the development of multiple new synthetic data sources.
For application-oriented research aiming at practically relevant insights, it is not just important to conduct computational experiments, but also to design realistic models in the first place. Addressing a so-far often neglected aspect of reality, in Parts III and IV, we contribute to popularizing the study of collective decision making problems that take into account that such problems often take place in a dynamic and changing environment, e.g., where agents change their preferences over time. In Chapter 6, we study a new method to evaluate the robustness of election winners to random noise, and identify (different types of) extremely non-robust winners in real-world elections that cannot be identified using classic worst-case approaches. Lastly, in Chapters 7 and 8, we analyze problems related to minimally adapting a stable matching to reestablish stability in case of changing external requirements or agents' preferences from an algorithmic and experimental perspective.
Kollektive Entscheidungsprobleme beschreiben Situationen, in denen die möglicherweise widersprüchlichen Präferenzen verschiedener Individuen in eine Kompromisslösung aggregiert werden müssen. Diese Arbeit befasst sich mit zwei solcher Probleme. Erstens, Wahlen, bei denen "Wähler" Präferenzen über "Kandidaten" ausdrücken und ein "gewinnender" Kandidat bestimmt werden muss. Zweitens, stabile Zuordnungen, bei denen jedes Individuum Präferenzen über die Anderen hat und eine stabile Zuweisung der Individuen zueinander gefunden werden muss.
Das Hauptziel dieser Arbeit ist es, den Weg für mehr anwendungsorientierte theoretische und experimentelle Forschung zu kollektiven Entscheidungsproblemen zu bereiten. Hierzu erweitern wir in Teil 1 und 2 den Werkzeugkasten für computergestützte Experimente. Solche Experimente können zum Beispiel dazu verwendet werden, die Laufzeit eines Algorithmus, die Ähnlichkeit zweier Mechanismen oder die Qualität einer Heuristik zu evaluieren. Sie haben daher das Potenzial, theoretische Forschung durch praktische Erkenntnisse zu ergänzen, zu überprüfen und ihr die Richtung zu weisen. Im Detail formulieren wir in Kapitel 2 einen Katalog von Herausforderungen, die man bei der Durchführung solcher Experimente meistern muss, und stellen mit der "map of elections" eine neue Methode für die Planung und Auswertung von Experimenten mit Wahlen vor. Im anschließenden Kapitel 3 präsentieren wir eine von uns zusammengestellte umfangreiche Sammlung von realen Präferenzdaten, die wir anschließend klassifizieren, analysieren und verwenden, um einige klassische Fragen der Sozialwahltheorie zu beantworten. In Kapitel 4 wenden wir uns synthetischen Datenquellen zu und werfen einen genaueren Blick auf das beliebte Mallows Modell. Im ersten Teil dieses Kapitels stellen wir etablierte Wege zur Nutzung des Mallows Modells in Frage. Außerdem führen wir eine neue Parametrisierung des Modells ein, dessen Verhalten sich besser mit realen Präferenzdaten deckt. Im zweiten Teil des Kapitels beschreiben wir einen neuen Ansatz für das sogenannte Präferenzlernproblem. Außerdem demonstrieren wir Nutzungsmöglichkeiten dieses Ansatzes zur Anpassung von (Mischungen von) Mallows Modellen an unsere zuvor gesammelten realen Daten, um ein besseres Verständnis für die Daten und das Mallows Modell zu erlangen. Abschließend konstruieren wir in Kapitel 5 eine "map of stable matching instances", die verschiedene Instanzen stabiler Zuordnungsprobleme visualisiert. Mithilfe der erstellten Karten analysieren wir die Beziehung zwischen Instanzen und visualisieren Ergebnisse von Experimenten.
Um praktisch relevante Forschungsergebnisse zu erzielen, ist es—neben der Nutzung aussagekräftiger Experimente—wichtig realistische Modelle zu verwenden. In Teil 3 und 4 studieren wir verschiedene kollektive Entscheidungsprobleme, die in dynamischen und sich verändernden Umgebungen auftreten, zum Beispiel, wenn Individuen im Laufe der Zeit ihre Präferenzen ändern. Da solche dynamischen Aspekte von realen kollektiven Entscheidungsproblemen in der bisherigen Forschung kaum betrachtet wurden, stellen Teil 3 und 4 somit einen Beitrag zur Popularisierung der Analyse von realistischeren Modellen dar. Genauer untersuchen wir in Kapitel 6 eine neue Methode zur Messung der Robustheit von Wahlgewinnern hinsichtlich zufälliger Veränderungen in den Präferenzen. Diese Methode erlaubt es uns verschiedene Arten von extrem unrobusten Gewinnern in realen Wahlen zu identifizieren. Zuletzt (in den Kapiteln 7 und 8) analysieren wir algorithmisch und experimentell Probleme rund um die minimale Anpassung von Zuordnungen, um deren Stabilität wiederherzustellen, nachdem sich externe Anforderungen oder die Präferenzen der Individuen geändert haben.
