DROPS

Document

DOI: 10.4230/LIPIcs.FORC.2025.20

Group Fairness and Multi-Criteria Optimization in School Assignment

Authors: Santhini K. A., Kamesh Munagala, Meghana Nasre, and Govind S. Sankar

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract

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.

Cite as

Santhini K. A., Kamesh Munagala, Meghana Nasre, and Govind S. Sankar. Group Fairness and Multi-Criteria Optimization in School Assignment. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{k.a._et_al:LIPIcs.FORC.2025.20,
  author =	{K. A., Santhini and Munagala, Kamesh and Nasre, Meghana and S. Sankar, Govind},
  title =	{{Group Fairness and Multi-Criteria Optimization in School Assignment}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.20},
  URN =		{urn:nbn:de:0030-drops-231471},
  doi =		{10.4230/LIPIcs.FORC.2025.20},
  annote =	{Keywords: School Assignment, Approximation Algorithms, Group Fairness}
}

Search Results

Documents authored by S. Sankar, Govind

Group Fairness and Multi-Criteria Optimization in School Assignment

Abstract

Cite as

Thanks for your feedback!

Could not send message