{"id":"a317364f-88e8-4f4f-b118-313a295bc016","arxiv_id":"2606.07285","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"New lower bound instance showing α-core empty below 2.1508 in proportionally fair clustering, plus exact α_m* thresholds for m=3..6 in Droop quota cases via MILP search and direct proofs.","lead":"The paper finds a clustering instance where the α-core fairness property fails for every α below 2.1508, raising the previous lower bound of 2. It also computes exact existence thresholds for small numbers of candidate centers in a related Droop quota setting.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest assumption concerns whether the reduction is w.l.o.g. for the optimal (highest) lower bound. That assumption would matter only if the paper claimed 2.1508 is tight; it does not. The exhibited instance stands on its own. Hence the identified assumption is not load-bearing for the stated central claim.","tokens_in":1764,"tokens_out":309,"duration_ms":16403,"concrete_test":"Extract the explicit point set, metric, and candidate centers for the 2.1508 instance; formulate the α-core emptiness condition as an optimization problem and solve it (or enumerate all k-subsets if k is small) to confirm that the worst-case violation ratio is at least 2.1508.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the existence of one concrete instance whose α-core is empty for all α < 2.1508. The reduction to a structured family is used only to discover candidate instances via MILP; once an instance is produced, its validity is independent of whether the family is exhaustive. The paper states that the small-m Droop-quota thresholds are accompanied by direct (non-MILP) proofs, and the main instance is presented as output of the same framework. No step in the argument for existence of this particular instance is left unsupported once the instance is exhibited.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1858,"tokens_out":343,"duration_ms":12949,"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.","major_comments":[],"minor_comments":[{"comment":"§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.","section":null},{"comment":"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.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[],"tokens_in":1337,"tokens_out":100,"duration_ms":7502,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The headline result is a new lower-bound instance showing the alpha-core can be empty for every alpha below 2.1508. That tightens the seven-year-old gap between the known (1+sqrt(2)) upper bound and the previous 2 lower bound. They also compute the exact thresholds alpha_m* for Droop-quota instances with m=3 to 6 centers, backed by direct proofs rather than MILP certificates.\n\nThe work connects Hare and Droop variants of the core, narrows the search to a structured family of instances, and uses MILP to locate candidates. For the small-m cases the direct proofs are a clear plus; they stand on their own once written out. The main instance is presented as output of the same process, and its validity does not depend on the family being exhaustive.\n\nThe main soft spot is that the 2.1508 figure rests on one specific instance whose correctness must be checked by hand or by independent verification of the MILP output. The abstract does not include the instance or the formulation details, so a referee would need those to confirm there are no hidden errors in the reduction or the objective. That is a standard check rather than a fatal gap.\n\nThis is aimed at researchers working on core notions in fair clustering and algorithmic game theory. Anyone tracking the alpha-core gap will want the new numbers. The paper shows clear thinking on the problem and honest engagement with the prior bounds, so it deserves a serious referee.","headline":"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.","tokens_in":2328,"tokens_out":382,"would_cite":true,"duration_ms":11278,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"There exists a clustering instance whose α-core is empty for every α below 2.1508.","keywords":["proportionally fair clustering","alpha-core","lower bounds","Hare core","Droop core","metric clustering","MILP"],"falsifier":"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.","tokens_in":2671,"feed_emoji":"","tokens_out":679,"duration_ms":24139,"temperature":0.7,"pith_summary":"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.","feed_headline":"Instance shows α-core empty below 2.1508","feed_subtitle":"Raises known lower bound on when core clusterings are guaranteed from 2 to 2.1508.","key_machinery":"The α-core, the requirement that no sufficiently large group of agents is collectively underrepresented by more than factor α in the chosen centers.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Instance voids α-core below 2.1508","α-core empty below 2.1508","Core threshold raised to 2.1508","No α-core for α below 2.1508"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The worst-case empty-core instances lie inside the reduced family of highly structured clustering instances.","fun_headline_variants_meta":{"raw":{"variants":["Instance voids α-core below 2.1508","α-core empty below 2.1508","Core threshold raised to 2.1508","No α-core for α below 2.1508"]},"model":"grok-4.3","cost_usd":0.00724,"raw_usage":{"total_tokens":3392,"prompt_tokens":777,"num_sources_used":0,"completion_tokens":60,"cost_in_usd_ticks":72399500,"prompt_tokens_details":{"text_tokens":777,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2555,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":777,"tokens_out":60,"duration_ms":19064,"temperature":1.0,"reasoning_tokens":2555,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-27T20:22:34.671188+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}