Improved Lower Bounds for Proportionally Fair Clustering
For researchers in algorithmic fairness, this work tightens the theoretical understanding of proportional fairness in clustering, though the improvement is incremental.
The paper improves the lower bound for proportionally fair clustering from α < 2 to α < 2.1508, narrowing the gap with the known upper bound of 1+√2. It also provides exact thresholds for Droop quota clustering with small numbers of centers.
We study proportionally fair clustering, where a set of $k$ centers must be chosen from a metric space to represent $n$ agents, and no sufficiently large group of agents should be collectively underrepresented. One of the central notions of fairness in this setting is the $α$-core. The existence of clusterings in the $(1+\sqrt{2})$-core was established by Chen et al. [2019], who also showed instances where the $α$-core is empty for every $α< 2$. Closing this gap has remained an open problem for seven years. We make progress from the lower-bound side by providing an instance whose $α$-core is empty for every $α< 2.1508$. Our techniques rely on establishing connections between variants of the core, namely the Hare core and the Droop core; reducing the search for optimal empty-core instances to a highly structured family of clustering instances; and using a Mixed Integer Linear Program (MILP) to search for optimal lower-bound instances within this reduced space. Using this framework, we also determine tight bounds for Droop quota clustering instances with a small number of possible candidate centers and a single center to be selected. For each number of centers $m \in \{3,4,5,6\}$, we give the exact threshold $α_m^*$ such that an $α_m^*$-core clustering always exists, while for every $α< α_m^*$ there is an instance with $m$ centers whose $α$-core is empty. Although these values were originally found through computer-aided search, we also provide direct proofs that do not rely on MILP certificates.