Probabilistic Separation and Fairness in Graph Partitioning and Assignment

Abstract

As algorithms increasingly govern societal decision-making systems, algorithmic fairness has become an essential requirement to prevent these systems from perpetuating systemic bias. While fairness can be broadly defined by the principle that similar entities should receive similar outcomes, mathematically rigorous definitions of equitable treatment are crucial to evaluate these algorithms. These definitions and their formulation differ greatly depending on the context in which they are studied. This dissertation investigates two such formulations: Group Fairness in resource allocation, and Separation Fairness in graph partitioning.We first study an assignment problem between students and schools. In this setting, we enforce Group Fairness, which requires that various student demographic groups are treated equitably. We design algorithms that trade off computational efficiency and capacity violation in schools to achieve this goal. We show that our techniques easily extend to accommodate arbitrary covering constraints for multi-criteria optimization.Next, we introduce the notion of Separation Fairness in the context of randomized graph partitioning. Fundamentally, this requires that nearby vertices in the graph are assigned to the same part with high probability, guaranteeing a probabilistic version of continuity that prevents partition boundaries from arbitrarily `cracking' specific neighborhoods. We design randomized algorithms for Low Diameter Decompositions that satisfy this requirement, ensuring that the probability of separating any pair of vertices lies in a range determined only by the distance between them. We support these results by advancing the theory of metric embeddings, presenting new approximation algorithms for embedding general metrics into hierarchically separated trees. We then apply this framework to political redistricting and show that for grid graphs, widely-used sampling methods satisfy separation fairness. This provides a theoretical basis for the empirical observation that these sampling methods preserve local community structure.