{"id":"9f0a9a6d-1845-482e-a36c-3beb6218ac81","arxiv_id":"1908.05433","paper_version":3,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The price of connectivity, the worst-case ratio between the best connected fairness guarantee and the unconstrained one, is 1/k for graphs with a cut vertex that splits into k pieces, at least 3/4 for biconnected graphs with two agents, and 1/(m−n+1) for paths and stars.","lead":"This paper measures how much fairness is lost when goods arranged on a graph must be split into connected pieces, introducing the price of connectivity. It gives exact worst-case ratios for paths, stars, and all two-agent cases up to a conjecture, plus the optimal envy relaxation for every graph with two agents.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader's weakest assumptions—additivity and reliance on prior G-MMS existence results—are the same places where a hidden failure would most plausibly enter, but neither is a load-bearing concern in context. The additivity restriction is explicitly stated before the PoC results and is standard for maximin-share work, so it limits scope without undermining the proved theorems. The dependency on Bouveret et al. Thm 5.4 and Lonc–Truszczynski Cor. 2 is external, but both are published results and are used exactly as stated; a failure there would affect the interpretation of Corollary 3.2 and Theorem 3.17, but that is a literature risk, not an internal inconsistency. I re-examined the most intricate proofs, including Lemma 3.5, Theorem 3.3, Theorem 3.16, Proposition 3.21, and Theorem 4.3, and found the arguments coherent. The paper's own stated open conjecture for highly connected graphs is appropriately flagged and does not contradict the claims accepted by the reader. Therefore the verdict should remain unchanged.","tokens_in":28315,"tokens_out":44499,"duration_ms":466059,"concrete_test":"Brute-force verification for all connected graphs on up to 7 vertices: compute the minimal k from Theorem 4.3 condition (1), then exhaustively search for identical-binary-utility EFk allocations and compare the resulting threshold with condition (1); any mismatch would disprove the EFk characterization.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The central claims—the PoC bounds in Section 3 and the EFk characterization in Theorem 4.3—are supported by detailed, parameter-free proofs. I re-checked the potentially delicate steps: Lemma 3.5's value-decrease argument is valid because the high part under u' inherits a lower bound from the original utility; Theorem 3.3's spanning-tree walk works because terminal subtrees are all at most 1/2, so any subtree reaching 1/(2k) would produce a connected bipartition with both parts at least 1/(2k); Theorem 3.16's extension of an MMS partition to a connected partition preserves the value bound since goods are nonnegative; Proposition 3.21's IPS algorithm has valid monotonicity and case analysis; and Theorem 4.3's switch operations are internally consistent. The additivity assumption is explicit, standard, and confined to Section 3. The only inherited dependencies are Bouveret et al. Thm 5.4 and Lonc–Truszczynski Cor. 2, both published and correctly cited. I found no internal gap that would change the reader's accept verdict.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the fair allocation of indivisible goods that form a connected undirected graph, with the requirement that each agent receive a connected bundle. It introduces the price of connectivity (PoC) as the worst-case ratio between the graph-restricted maximin share and the unconstrained maximin share. For two agents, the paper proves PoC = 1/k for graphs of connectivity 1 (where k is the maximum number of components after deleting a vertex), PoC ≥ 3/4 for biconnected graphs, and exact PoC values for several families, including complete graphs with a matching removed; it also proposes a conjecture, verified for a nontrivial class, that would settle the two-agent case. For general n, it establishes a universal lower bound 1/(m−n+1) and tight bounds for paths and stars, introducing the indivisible proportional share (IPS) property in the process. On the envy-freeness side, the paper characterizes, for every graph and two agents, the smallest k for which an EFk allocation is always guaranteed, via a block-decomposition condition; it also characterizes the trees and complete bipartite graphs that guarantee EF1 for three agents. Most guarantees come with polynomial-time algorithms.","tokens_in":28432,"tokens_out":17924,"duration_ms":170275,"significance":"The paper gives a clean, parameter-free quantitative framework for the fairness loss caused by connectivity constraints, with tight results for several major graph classes and a complete two-agent EFk characterization. The PoC notion meaningfully connects graph connectivity to MMS approximation, and the lower-bound constructions are explicit utility functions rather than existential arguments. The paper also introduces IPS, a new proportionality relaxation stronger than several existing notions, and shows it is always achievable on paths; this is likely to be of independent interest. The proofs are detailed and largely constructive, with polynomial-time algorithms for most theorems, including the 3/4-MMS approximation for biconnected graphs in Appendix A. The main open conjecture (Conjecture 3.13) is well-motivated and is verified for complete graphs with a matching removed, lending further credibility to the proposed framework.","major_comments":[],"minor_comments":[{"comment":"The proof uses the assertion that any superset of an IPS bundle is also IPS, but this is stated without proof. The claim is true for the IPS constants used (since c ≤ 1), but it requires a short argument; moreover, in Case 2 the application of the non-IPS condition uses sets Y and Z that may include goods already allocated to earlier agents, so the proof should explicitly invoke monotonicity of u and restrict the set B to the goods available at the relevant time. Please add these details.","section":"Section 3.2, Proposition 3.21"},{"comment":"The dichotomy 'each part either has value at most αx, or at least y+(1−α)x' is correct but terse; a one-line explanation (at least one part must have value at most αx, hence the other part has value at least the total minus αx) would prevent reader confusion.","section":"Section 3.1, Lemma 3.5"},{"comment":"The upper-bound proofs for paths rely on 'one can check' statements asserting that some part has value at most 1 in any connected n-partition. Please add a short pigeonhole argument: since high-value goods are separated by value-1 goods, a connected part avoiding all high-value goods can contain at most one unit-valued good.","section":"Section 3.2, Theorem 3.22"},{"comment":"The proof of Theorem 4.3 is intricate, and the switch operations in Cases 1 and 2 are described with the help of Figures 4 and 5. A sentence explicitly pointing the reader to the relevant figure when the first switch operation is introduced would improve readability.","section":"Section 4.1, Theorem 4.3"},{"comment":"There are several typographical issues, such as 'an d' in the abstract, 'und irected' in the first sentence, and inconsistent spacing in some references; these should be cleaned up in the final version.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is a strong fit for the journal and the contributions are likely to be influential. The only substantive concern is the missing justification in the IPS proof of Proposition 3.21, which is a local fix and should not affect the validity of the results. I have no concerns about novelty or attribution; the related work is comprehensive and the self-citations are appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one thing to know: this paper introduces the price of connectivity and actually resolves it for several nontrivial graph classes. It is a real result, not a rebranding. The PoC cleanly separates the graph-imposed fairness loss from the unconstrained MMS problem, and the authors get exact bounds for paths, stars, and connectivity-1 graphs, a tight 3/4 for biconnected graphs, and a complete EFk characterization for two agents. The proof style is what you want in this area: explicit adversarial utility functions, averaging arguments, and graph-theoretic tools like ear decompositions and block trees used correctly. The IPS property for paths is a nice contribution on its own. No fitted parameters, no data, just parameter-free derivations, plus polynomial-time algorithms for most guarantees.\n\nWhat could be softer is quite soft. The additivity assumption for the maximin part is standard and clearly stated, so I do not count it as a flaw. A few expositions are terse: the monotonicity claim inside the IPS algorithm is stated without proof, though it follows directly from the definitions. The results also inherit from Bouveret et al. and Lonc-Truszczynski for the beta=1 cases; those are published and cited properly, so that is fine. The main open spot is the linkedness conjecture for higher connectivity, but the authors flag it explicitly and verify it for a nontrivial family. I checked the potentially delicate steps in Theorem 3.3, Theorem 3.16, and Theorem 4.3 and found no internal gaps.\n\nWho is this for: anyone in computational social choice or fair division, and graph theorists who want to see their tools used in allocation. I would bring it to my reading group and would likely cite it in future work. It deserves a serious referee, and a careful referee will probably come back with minor revision, not rejection.","headline":"Genuinely new measure with clean exact results; worth a careful read and a serious referee.","tokens_in":29007,"tokens_out":1606,"would_cite":true,"duration_ms":18351,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":null,"created_at":"2026-08-14T13:16:13.841891+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":null,"supporting_citations":[],"review_version":1}