Abstract
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+√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 ∈ {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.