Fair Committee Selection under Ordinal Preferences and Limited Cardinal Information

Summary

We study fair k-committee selection under an egalitarian objective. Here, we are given a set of agents partitioned into groups, and each agent reports a complete ranking over all other agents. The task is to select a committee of size k that satisfies minimum representation constraints for each group while minimizing the maximum cost incurred by any agent. Without access to cardinal distances, constant distortion guarantees are not possible for k ≥ 3 (Burkhardt et al. 2024). In light of this, we model the problem as the ordinal fair k-center problem with limited access to distance queries. In this query-efficient setting, our main result is a 5-distortion algorithms using O(k log2 k) queries; along the way, we obtain a 3-distortion algorithm using O(k2) queries.