Perpetual Individualized Fair Rank Aggregation

Abstract

Kollektive Entscheidungsprozesse sind oft kein isoliertes einmaliges Ereignis, sondern wiederholen sich häufig, wobei sich die Wählerschaft, die Präferenzen und die Alternativen ständig ändern. In dieser Diplomarbeit untersuchen wir eine bestimmte Variante des Problems der Rank Aggregation. Wir stellen ein Modell vor, das die zeitlichen Aspekte eines Präferenzaggregationsszenarios berücksichtigt. Um Fairness zu gewährleisten, enthält unser Modell Mechanismen zur Aufrechterhaltung einer proportionalen Vertretung im Laufe der Zeit. Wir erweitern diese Konstellation, indem wir einen besonderen Wähler einführen, der eine besondere Bedeutung und daher einen größeren Einfluss auf das Ergebnis hat. Wir passen unser Modell an die Situation an, in der der besondere Wähler andere Anforderungen als die anderen hat, sodass die Proportionalität unter Wählerinnen und Wählern weiterhin gewahrt bleibt. Zu diesem Zweck erweitern wir den Formalismus des Perpetual Votings auf die Rank Aggregation. Wir führen neue Aktualisierungsregeln (AR) ein und analysieren deren Verhalten in Kombination mit drei bekannten Social-Preference-Funktionen (SPFs): Borda, Kemeny und Squared Kemeny. Um die Fairness zu bewerten, entwickeln wir axiomatische Eigenschaften. Unsere theoretische Analyse zeigt, dass verschiedene Konfigurationen unterschiedliche Stärken und Einschränkungen haben. Darüber hinaus untersucht unser Modell mehrere Strategien zur Initialisierung der Gewichte, einschließlich Szenarien, in denen der besondere Wähler priorisiert wird. Durch Simulationen bewerten wir, wie sich verschiedene Kombinationen von AR und SPFs in Bezug auf langfristige Proportionalität auswirken. Unsere Ergebnisse zeigen, dass die Wahl der SPF in Bezug auf Fairness wichtiger ist als die der AR, aber einige AR sind dennoch vielversprechender als andere. In einigen Fällen beobachten wir, dass axiomatische Ergebnisse das reale Durchschnittsverhalten nicht vollständig widerspiegeln. Abschließend demonstrieren wir die praktische Relevanz unseres Modells, indem wir einen Entwurf für fairnessorientierte Empfehlungssysteme mit mehreren Interessengruppen vorstellen. Diese Arbeit liefert einen theoretischen Beitrag zum Verständnis von Fairness bei sich ständig ändernden kollektiven Entscheidungsprozessen und unterstützt die Entwicklung gerechter algorithmischer Systeme in der Praxis.

In collective decision making, the process is often not an isolated one-time event. It is often repeated, with evolving voters, voter preferences, and alternatives. We study a particular variant of the rank aggregation problem, focusing on decision-making over time. We introduce a model that considers the temporal aspects of a preference aggregation scenario that produces a ranking in each round while taking the evolving voter preferences into account. In order to ensure fairness, our model incorporates mechanisms to maintain proportional representation over time. We further extend this setting by introducing a special voter who has special importance and, consequently, greater influence over the outcome. We adapt our model to the setting where the special voter has different representation requirements compared to others, while still maintaining the proportionality among voters. To this end, we extend the formalism of perpetual voting to rank aggregation. Our formalism adapts update rules from perpetual voting, which is based on approval ballots, and also introduces novel update rules for ranking-based outcomes. We analyze the behavior of the update rules in combination with three prominent social preference mechanisms: Borda, Kemeny, and Squared Kemeny. To evaluate fairness, we develop axiomatic properties that capture proportionality and equitable influence across time. Our theoretical analysis shows that different settings have different strengths and limitations. Furthermore, our framework explores multiple weight initialization strategies, including scenarios where the special voter is prioritized. Through simulations, we assess how various combinations of update rules and social preference mechanisms perform with respect to long-term fairness and proportionality. Our results indicate that the choice of the social preference mechanism is more important than the update rule in terms of fairness but some update rules are still more promising than others. In some cases, we observe that axiomatic results do not always capture the real average behavior in its full complexity. Finally, we demonstrate the practical relevance of our model by proposing a design for fairness-aware multi-stakeholder recommender systems. Our approach serves as a design concept for recommendation algorithms that aim to balance fairness and different stakeholders' objectives with user-centric accuracy. This thesis thus contributes both to the theoretical understanding of fairness in evolving collective decisions over time and to the practical development of equitable algorithmic systems.