The Price of Fairness in Algorithmic Decision-Making

Abstract

Algorithms play a fundamental role in modern decision-making, impacting economic structures, cultural landscapes, and resource allocation at unprecedented scales. While optimization techniques often prioritize efficiency—finding solutions quickly with minimal resources—many real-world applications require an additional consideration: fairness. This thesis explores the intricate trade-offs between efficiency and fairness in algorithm design, focusing on two key do-mains: fair division and fair hierarchical clustering.

In the first part, I examine the fair division problem, which seeks to distribute resources among stakeholders in an equitable and efficient manner. I introduce novel approaches for balancing fairness constraints with computational feasibility, investigating both offline and online settings. In offline fair division, I analyze classical notions such as envy-free allocations and extend them to more general settings, including weighted agent priorities and multigraph valuation models. In the online setting, where decisions must be made without full knowledge of future arrivals, I present new algorithms for fair resource allocation, including solutions for the online Santa Claus problem and class-fair bipartite matching.

The second part of this thesis focuses on fair hierarchical clustering, a problem central to machine learning and data analysis. Many clustering algorithms reinforce biases in data representation, disproportionately impacting marginalized groups. I develop novel fair clustering algorithms that balance demographic representation while preserving computational efficiency.My work introduces the first explainable algorithm for fair hierarchical clustering and provides near-optimal polylogarithmic approximation guarantees, significantly improving upon prior results.

By leveraging techniques from combinatorial optimization, game theory, and online algorithms, this thesis provides theoretical insights and practical methodologies for designing algorithms that uphold fairness constraints without sacrificing efficiency. These contributions have broad implications for resource allocation, machine learning, and algorithmic fairness in large-scale systems.