- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies proportional fairness in hierarchical clustering. Instead of requiring fairness for one partition into k clusters, it considers whether an entire hierarchy can satisfy proportional fairness.
The authors introduce two notions:
- Local core: Every binary split must be proportionally fair within its parent cluster.
- Global core: Every k-clustering appearing in the hierarchy must satisfy proportional fairness, with blocking coalitions of size at least n/k. They consider two agent-loss functions: maximum distance to another cluster member and average distance to cluster members.
The distinction between the two core notions is meaningful. The paper also addresses an open problem concerning the existence of non-centroid core-stable clustering for k=2.
Critical strengths
Resolving the existence question for non-centroid k=2 clustering is interesting independently of hierarchical clustering.
Critical weaknesses
The algorithmic result still remains open while the paper proves existance for 2-clustering.
There are no experiments!
Questions for authors
Is the factor 2 in the coalition-size threshold necessary to obtain any constant-factor approximation?
Do you have any algorithms that you think will work well on the 2-clustering case?
Can you add some experiments on tadesoffs of fairness vs. quality of clustering?
Official comment answering Reviewer ALc7
Thank you for your feedback.
Coalition size threshold for global core
We address this question in the global official comment above.
Algorithms for 2-Clustering
With the maximum loss objective, the GreedyCapture algorithm by Caragiannis et al. yields a non-centroid clustering in the 2-core. Applying it recursively thus gives a hierarchy in the local 2-core. Finding an exact core-stable 2-clustering efficiently remains open.
Empirical evaluation
Please refer to our answer in the global official comment above.