An official website of the United States government
We study the problem of fair k-median where each cluster is required to have a fair representation of individuals from different groups. In the fair representation k-median problem, we are given a set of points X in a metric space. Each point x ∈ X belongs to one of ℓ groups. Further, we are given fair representation parameters αj and β_j for each group j ∈ [ℓ]. We say that a k-clustering C_1, ⋅⋅⋅, C_k fairly represents all groups if the number of points from group j in cluster C_i is between α_j |C_i| and β_j |C_i| for every j ∈ [ℓ] and i ∈ [k]. The goal is to find a set of k centers and an assignment such that the clustering defined by fairly represents all groups and minimizes the ℓ_1-objective ∑_{x ∈ X} d(x, ϕ(x)). We present an O(log k)-approximation algorithm that runs in time n^{O(ℓ)}. Note that the known algorithms for the problem either (i) violate the fairness constraints by an additive term or (ii) run in time that is exponential in both k and ℓ. We also consider an important special case of the problem where and for all j ∈ [ℓ]. For this special case, we present an O(log k)-approximation algorithm that runs in time.
more »
« less
This content will become publicly available on January 1, 2026
Group Fairness and Multi-Criteria Optimization in School Assignment
We consider the problem of assigning students to schools when students have different utilities for schools and schools have limited capacities. The students belong to demographic groups, and fairness over these groups is captured either by concave objectives, or additional constraints on the utility of the groups. We present approximation algorithms for this assignment problem with group fairness via convex program rounding. These algorithms achieve various trade-offs between capacity violation and running time. We also show that our techniques easily extend to the setting where there are arbitrary constraints on the feasible assignment, capturing multi-criteria optimization. We present simulation results that demonstrate that the rounding methods are practical even on large problem instances, with the empirical capacity violation being much better than the theoretical bounds.
more »
« less
- PAR ID:
- 10598386
- Editor(s):
- Bun, Mark
- Publisher / Repository:
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- Date Published:
- Volume:
- 329
- ISSN:
- 1868-8969
- ISBN:
- 978-3-95977-367-6
- Page Range / eLocation ID:
- 20:1-20:20
- Subject(s) / Keyword(s):
- School Assignment Approximation Algorithms Group Fairness Theory of computation → Design and analysis of algorithms
- Format(s):
- Medium: X Size: 20 pages; 785985 bytes Other: application/pdf
- Size(s):
- 20 pages 785985 bytes
- Right(s):
- Creative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccess
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Fueled by algorithmic advances, AI algorithms are increasingly being deployed in settings subject to unanticipated challenges with complex social effects. Motivated by real-world deployment of AI driven, social-network based suicide prevention and landslide risk management interventions, this paper focuses on a robust graph covering problem subject to group fairness constraints. We show that, in the absence of fairness constraints, state-of-the-art algorithms for the robust graph covering problem result in biased node coverage: they tend to discriminate individuals (nodes) based on membership in traditionally marginalized groups. To remediate this issue, we propose a novel formulation of the robust covering problem with fairness constraints and a tractable approximation scheme applicable to real world instances. We provide a formal analysis of the price of group fairness (PoF) for this problem, where we show that uncertainty can lead to greater PoF. We demonstrate the effectiveness of our approach on several real-world social networks. Our method yields competitive node coverage while significantly improving group fairness relative to state-of-the-art methods.more » « less
-
We develop a rounding method based on random walks in polytopes, which leads to improved approximation algorithms and integrality gaps for several assignment problems that arise in resource allocation and scheduling. In particular, it generalizes the work of Shmoys & Tardos on the generalized assignment problem to the setting where some jobs can be dropped. New concentration bounds for random bipartite matching are developed as well.more » « less
-
The 2018 John Bates Clark medal of the American Economic Association was awarded to Parag Pathak for his contributions to our understanding of the impacts of educational policies. Both the theory and the empirical research was notable for taking the constraints facing administrators seriously. As a result, Parag’s research led directly to educational reforms in many large U.S. cities and abroad. The leading example is Parag (and co-author’s) research on school assignment mechanisms which led many school districts to institute fairer and more efficient procedures for allocating students to schools. The institutional detail Parag learned in working on the assignment problem led to innovative empirical work on the impacts of different types of schools, most notably of charters, which was suggestive of the characteristics of both successful schools and of the types of students who gained from being enrolled in them. His recent work utilizes the data that has been generated by the new assignment rules to provide complete frameworks for the quantitative analysis of the benefits of different assignment mechanisms, and has an enlightening demonstration of those benefits in New York high schools.more » « less
-
The 2018 John Bates Clark medal of the American Economic Association was awarded to Parag Pathak for his contributions to our understanding of the impacts of educational policies. Both the theory and the empirical research was notable for taking the constraints facing administrators seriously. As a result, Parag’s research led directly to educational reforms in many large U.S. cities and abroad. The leading example is Parag (and co-author’s) research on school assignment mechanisms which led many school districts to institute fairer and more efficient procedures for allocating students to schools. The institutional detail Parag learned in working on the assignment problem led to innovative empirical work on the impacts of different types of schools, most notably of charters, which was suggestive of the characteristics of both successful schools and of the types of students who gained from being enrolled in them. His recent work utilizes the data that has been generated by the new assignment rules to provide complete frameworks for the quantitative analysis of the benefits of different assignment mechanisms, and has an enlightening demonstration of those benefits in New York high schools.more » « less
