Proportional Hierarchical Clustering

Hierarchical clustering represents data at multiple levels of granularity, but proportional fairness is traditionally only defined for a single partition. We therefore study how it can be extended to an entire hierarchy. Building on prior work on proportional clustering, we introduce two notions: the local core, which requires proportional fairness at each split, and the global core, which requires it at every partition in the hierarchy. We study both notions under the assumption that an agent's loss (disutility) for a clustering is the maximum distance to other members of their cluster. We show that the two core notions are incomparable and that standard agglomerative clustering techniques fail to satisfy them. However, under the maximum loss objective, a hierarchical clustering in the local core always exists. On the way, we resolve an open question from Caragiannis et al. (2024) by showing that there always exists a non-centroid clustering in the core for k = 2, whereas for k ≥ 3 the core can be empty (even for Euclidean distances). For the global core, we show that even arbitrary approximations of it need not exist. However, doubling the coalition size threshold allows us to compute an outcome in the global 16-core for maximum-loss and global 8n-core for average-loss, where n is the number of data points.
This is joint work with Robert Bredereck, Eva Deltl, and Jannik Peters.