Pith. sign in

REVIEW 2 minor 19 references

Improved Lower Bounds for Proportionally Fair Clustering

T0 review · 0 major / 2 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read There exists a clustering instance whose α-core is empty for every α below 2.1508.

desk verdict The paper exhibits a concrete instance pushing the empty alpha-core threshold to 2.1508 and gives exact alpha_m* values for m=3-6 with direct proofs. read the letter →

arxiv 2606.07285 v1 pith:G27NP27E submitted 2026-06-05 cs.GT

Benjamin Cookson , Eva Deltl , Yeeseok Oh This is my paper · ORCID
classification cs.GT
keywords proportionallyfairclusteringalpha-corelowerboundsHarecoreDroopmetricMILP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper seeks to narrow the gap between the known lower bound of 2 and upper bound of roughly 2.414 on the smallest α such that every proportionally fair clustering instance admits an α-core solution. It exhibits a concrete instance where the α-core remains empty for all α less than 2.1508, using links between Hare-core and Droop-core variants together with a search over a restricted family of instances. A sympathetic reader would care because the result moves the feasible range for the exact threshold downward and supplies exact thresholds for small Droop-quota cases. The authors further supply non-computer-aided proofs for those small cases.

What carries the argument

The α-core, the requirement that no sufficiently large group of agents is collectively underrepresented by more than factor α in the chosen centers.

What would settle it

An explicit instance whose α-core is empty for some α at least 2.1508, or a proof that every instance admits a core clustering whenever α is at least 2.1508.

Watch

Extended reading notes

Core claim

We provide an instance whose α-core is empty for every α < 2.1508. This is obtained by linking variants of the core concept, restricting attention to a structured family of instances, and employing a mixed integer linear program to identify the worst-case lower bound within that family. For Droop quota clustering with few candidate centers and one center chosen, we determine the precise α_m^* for m from 3 to 6 such that an α_m^*-core always exists but smaller α do not guarantee it.

Load-bearing premise

The worst-case empty-core instances lie inside the reduced family of highly structured clustering instances.

Editorial extensions

If this is right

  • The α-core can be empty for every α up to at least 2.1508.
  • Exact thresholds α_m^* exist for Droop-quota single-center selection when the number of candidate centers is 3, 4, 5 or 6.
  • Hare-core and Droop-core notions are related in ways that help locate empty-core instances.
  • The MILP search over the reduced instance family produces verifiable lower bounds.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The exact threshold for guaranteed core existence therefore lies somewhere above 2.1508 and at or below 1 plus square root of 2.
  • The same reduction-plus-search approach may locate improved bounds for other proportional-fairness notions in clustering.
  • The direct proofs supplied for the small Droop cases indicate that the MILP-derived values can be confirmed by hand.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The manuscript studies proportionally fair clustering and the α-core. It exhibits a concrete instance whose α-core is empty for every α < 2.1508, improving the prior lower bound of 2 while the known upper bound remains 1 + √2. The construction is obtained by reducing the search to a structured family of instances, using MILP to identify candidates, and verifying the main instance directly; the paper additionally computes exact thresholds α_m^* for Droop-quota instances with m ∈ {3,4,5,6} candidate centers and supplies non-MILP proofs for those small cases.

Significance. If the exhibited instance is valid, the result narrows the seven-year gap on the α-core threshold. The combination of MILP-assisted discovery with independent direct proofs for the small-m Droop cases supplies both a concrete lower-bound witness and machine-checkable certificates, which are strengths under the journal’s standards for reproducible results.

minor comments (2)
  1. §3 (or wherever the structured family is defined): the precise statement that the reduction is used only for candidate generation, not for the validity argument of the final instance, should be stated explicitly once in the main text so that readers need not consult the skeptic note.
  2. The connection between Hare-core and Droop-core variants is invoked to justify the MILP encoding; a short self-contained paragraph recalling the definitions and the implication used would improve readability for readers outside the immediate sub-area.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The report correctly identifies the key contributions: the improved lower bound of 2.1508 via the MILP-guided instance, the connections between Hare and Droop cores, and the exact thresholds with direct proofs for small m. No major comments were raised, so we provide no point-by-point rebuttals below.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; explicit instance construction with independent verification

full rationale

The paper's central result is the explicit construction of one concrete clustering instance whose α-core emptiness for all α < 2.1508 is verified directly (via MILP output or direct proof). The reduction to a structured family is used only as a search heuristic to discover candidate instances; once an instance is exhibited, its validity as a lower-bound witness does not depend on the reduction being exhaustive. Small-m Droop-quota thresholds are accompanied by direct (non-MILP) proofs. No self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations appear in the derivation chain. The argument is self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

No free parameters, axioms, or invented entities are identifiable from the abstract; the contribution is computational search within a reduced instance family.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Lower Bounds for Proportionally Fair Clustering." pith.science (2026). https://pith.science/paper/G27NP27E

@misc{pith2026260607285,
  author       = {Pith},
  title        = {Pith review of: Improved Lower Bounds for Proportionally Fair Clustering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G27NP27E}},
  note         = {Machine review of arXiv:2606.07285}
}
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 $\alpha$-core. The existence of clusterings in the $(1+\sqrt{2})$-core was established by Chen et al. [2019], who also showed instances where the $\alpha$-core is empty for every $\alpha < 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 $\alpha$-core is empty for every $\alpha < 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 $\alpha_m^*$ such that an $\alpha_m^*$-core clustering always exists, while for every $\alpha < \alpha_m^*$ there is an instance with $m$ centers whose $\alpha$-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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 6 canonical work pages

  1. [1]

    Embeddings for Preferences, Not Semantics

    Embeddings for Preferences, Not Semantics , author=. arXiv preprint arXiv:2605.08360 , year=

    work page Pith review arXiv

  2. [2]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    On the edge of core (non-) emptiness: An automated reasoning approach to approval-based multi-winner voting , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

  3. [3]

    Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence , articleno =

    Peters, Dominik , title =. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence , articleno =. 2025 , doi =

    2025

  4. [4]

    Proportional Clustering, the

    Kellerhals, Leon and Peters, Jannik , journal=. Proportional Clustering, the. 2026 , publisher=

    2026

  5. [5]

    2024 , issue_date =

    Filtser, Arnold and Filtser, Omrit , title =. 2024 , issue_date =. doi:10.1007/s00454-023-00619-5 , journal =

    work page doi:10.1007/s00454-023-00619-5 2024

  6. [6]

    2021 , issue_date =

    Aronov, Boris and De Berg, Mark and Gudmundsson, Joachim and Horton, Michael , title =. 2021 , issue_date =. doi:10.1145/3459097 , journal =

    work page doi:10.1145/3459097 2021

  7. [7]

    Fair Transit Stop Placement: A Clustering Perspective and Beyond

    Fair Transit Stop Placement: A Clustering Perspective and Beyond , author=. arXiv preprint arXiv:2602.06776 , year=

    work page Pith review arXiv

  8. [8]

    Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems , pages =

    Ebadian, Soroush and Micha, Evi , title =. Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems , pages =. 2025 , publisher =

    2025

Show all 19 references
  1. [9]

    arXiv preprint arXiv:2511.19107 , year=

    The Core in Max-Loss Non-Centroid Clustering Can Be Empty , author=. arXiv preprint arXiv:2511.19107 , year=

  2. [10]

    Information Processing Letters , volume=

    Geometric stable roommates , author=. Information Processing Letters , volume=. 2009 , publisher=

    2009

  3. [11]

    Advances in Neural Information Processing Systems , volume =

    Cookson, Benjamin and Shah, Nisarg and Yu, Ziqi , title =. Advances in Neural Information Processing Systems , volume =

  4. [12]

    Advances in Neural Information Processing Systems , volume=

    Proportional fairness in non-centroid clustering , author=. Advances in Neural Information Processing Systems , volume=

  5. [13]

    Proceedings of the 36th International Conference on Machine Learning (ICML'19) , pages =

    Proportionally Fair Clustering , author =. Proceedings of the 36th International Conference on Machine Learning (ICML'19) , pages =. 2019 , volume =

    2019

  6. [14]

    Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) , series =

    Evi Micha and Nisarg Shah , title =. Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) , series =. 2020 , publisher =

    2020

  7. [15]

    and Chu, Sean Morota and Vollen, Jeremy , title =

    Aziz, Haris and Lee, Barton E. and Chu, Sean Morota and Vollen, Jeremy , title =. 2024 , publisher =. doi:10.1007/978-3-032-08560-3_9 , booktitle =

    2024 doi

  8. [16]

    Computing and Testing Pareto Optimal Committees , journal =

    Haris Aziz and J. Computing and Testing Pareto Optimal Committees , journal =. 2020 , doi =

    2020

  9. [17]

    Proceedings of the 38th International Conference on Neural Information Processing Systems , articleno =

    Kellerhals, Leon and Peters, Jannik , title =. Proceedings of the 38th International Conference on Neural Information Processing Systems , articleno =. 2024 , isbn =

    2024

  10. [18]

    Proceedings of the 38th International Conference on Neural Information Processing Systems , articleno =

    Caragiannis, Ioannis and Micha, Evi and Shah, Nisarg , title =. Proceedings of the 38th International Conference on Neural Information Processing Systems , articleno =. 2024 , isbn =

    2024

  11. [19]

    Proportionale Clusterings auf Graphen , url=

    Trinh, Phuoc Lucky , year=. Proportionale Clusterings auf Graphen , url=

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.