Seminars
View all Seminars | Download ICal for this eventAlgorithms for Fair Allocation on Graphs: Graph Cuts, Matching, and Beyond
Series: Ph.D. Colloquium
Speaker: Atasi Panda, Ph.D (Engg.) student, Dept. of CSA, IISc
Date/Time: May 22 10:00:00
Location: CSA Auditorium, (Room No. 104, Ground Floor)
Faculty Advisor: Prof. Anand Louis
Abstract:
Algorithms for resource allocation on graphs, including bipartite matching, graph cuts, and routing, underpin systems across domains as diverse as school admissions, hospital residency matching, content recommendation, federated learning, disaster containment, and last-mile routing. As these systems scale, ensuring equitable outcomes across different groups and individuals has become a fundamental concern. A substantial body of work formalizes fairness in these systems through bounds-based notions, which constrain the representation of each group on each platform via upper and lower bounds, and through envy-based notions, which compare allocations across agents. However, when such fairness considerations are imposed on combinatorial optimization problems on graphs like bipartite matching, graph cuts, and routing, existing techniques typically address either group fairness or individual fairness in isolation, leave the bounds rigid even when flexibility is desirable, and envy-based fair allocation has rarely been studied in settings where the graph induces a cost function that itself is computationally hard to evaluate. This thesis develops algorithms with provable guarantees that address these gaps across graph optimization settings and extends the study of fairness in graph optimization to a setting drawn from the fair allocation of chores.
The thesis is organized into two parts. Part I develops bounds-based fairness algorithms for three graph optimization problems. Disaster containment can be modeled as a graph-cut problem in which vertices represent demographic groups and must be protected from a source of infection. We give the first algorithm that simultaneously achieves group fairness on every realized cut and a prescribed protection probability for every individual vertex, via randomized rounding of a linear program. Building on this best-of-both-worlds paradigm, we study bipartite matching with group fairness constraints and item preferences. We present a unified LP-based framework that decomposes approximate fractional solutions into convex combinations of integer group-fair matchings, yielding polynomial-time algorithms under increasingly general structural assumptions on how items belong to groups. Moving beyond hard fairness bounds, we then study a soft alternative in which platforms incur convex costs based on group representation and present approximation algorithms based on minimum-cost flow, alongside matching hardness results.
Extending beyond bounds-based fairness, in Part II, we study envy-based fair allocation of routing tasks, where each agents cost is the Steiner Traveling Salesman tour (STSP) over their assigned orders. We consider envy-freeness up to one order (EF1) and envy-freeness up to any order (EFX), and study their existence, computation, and verification under STSP-induced costs. We show that approximate EF1 and EFX allocations can be computed in polynomial time whenever an approximate STSP can be computed efficiently. On the hardness side, we establish that verifying whether a given allocation is approximately EF1 or EFX is NP-hard, that computing an EFX allocation on weighted graphs is NP-hard even with two identical agents, and that computing a non-wasteful EF1 or EFX allocation is NP-hard even on unweighted trees, where cost evaluation is itself tractable. Together, these results characterize the landscape of envy-based fair allocation under hard-to-compute routing costs.