{"id":"18937508-48d7-4863-a4b6-cde75fa05155","arxiv_id":"2412.08572","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A proportional mechanism with payments achieves a tight 3/2 approximation to the optimal makespan in unrelated-machines scheduling, and achieves the exact optimum for normalized costs.","lead":"This paper proves that a proportional scheduling rule with payments can approximate the optimal makespan within a factor of 3/2, and that no better factor is possible. The result is the first tight bound for the price of proportionality in this classic scheduling problem, contrasting with logarithmic lower bounds for envy-free rules.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof misses the case where a merge at i=h is later moved to A_ell by a swap when h<ell; the 3/2 bound is repairable but not established as written.","rationale":"The paper's main positive result is Theorem 1. The mean-efficiency characterization, the payment formula, and the lower bound Theorem 2 are internally consistent. My concern is limited to a missing case in the proof of Theorem 1, not to a false statement of the theorem. The missing case can be closed with a short argument using the swap condition and the merge condition, so I do not think the result is wrong; the manuscript should be revised. This supports the reader's CONDITIONAL verdict, although the specific defect I identify is different from the 'reversed inequality' mentioned in the reader's rationale. I therefore keep the verdict unchanged, with partial agreement with the reader's diagnosis.","tokens_in":19253,"tokens_out":31849,"duration_ms":317816,"concrete_test":"Add to the proof of Theorem 1 a subcase for h < ell: after a merge at i = h sets A_h = B_ell union B_h, the only way A_ell can later become the union is a swap at i = ell, whose condition yields c_ell(B_ell union B_h) <= c_h(B_ell union B_h); combine this with the merge condition c_h(B_ell union B_h) <= (3/2)M. Verify no other iteration touches these bundles, since the pairing i -> m - i + k is an involution. If this argument is sound, Theorem 1 stands; if not, the 3/2 approximation claim is unproved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central 3/2 upper bound (Theorem 1) is not fully proved as written. In the proof's case analysis, after enumerating A_ell in {empty, B_ell, B_h, B_ell union B_h}, the text asserts: 'The only way for A_ell to be set to B_ell union B_h is in the merge operation in Line 10 during the iteration with i = ell.' This is false when the partner index h = m - ell + k satisfies h < ell. The loop reaches i = h first: if the merge condition at i = h holds, it sets A_h <- B_ell union B_h and A_ell <- empty; later at i = ell, the swap step can move this union to A_ell. The written proof has no bound for this path. The gap is repairable: the merge at i = h guarantees c_h(B_ell union B_h) <= (3/2)M, and the later swap occurs only if c_ell(B_ell union B_h) < c_h(B_ell union B_h), so c_ell(B_ell union B_h) <= (3/2)M follows. But because this case is omitted, the text does not currently establish the theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies fair mechanisms for unrelated-machine scheduling, viewing jobs as chores and machines as agents, in a quasi-linear model with payments. It defines proportionality (Definition 2.4) and characterizes proportionable allocations by a mean-efficiency condition (Theorem 6). The main results are a proportional mechanism with a 3/2 makespan approximation for general instances (Theorem 1), a matching lower bound (Theorem 2), an exact proportional mechanism for normalized instances (Theorem 3), analogous results for goods allocation (Theorems 4 and 5), a characterization of approximately envy-freeable allocations (Theorem 8), and a result showing that the known envy-free lower-bound technique does not extend to approximate cyclic envy-freeness (Theorem 9).","tokens_in":19455,"tokens_out":33016,"duration_ms":279699,"significance":"If the main theorem is established, the paper gives a striking contrast with the logarithmic impossibility for envy-freeness: proportionality with payments has a tight constant price of fairness, 3/2, for the makespan objective. The mean-efficiency characterization is elegant and reduces proportionality to a simple total-cost condition with an explicit payment formula. The lower-bound construction is explicit and the normalized-instance exact result is a clean graph argument. The goods-allocation and approximate-envy-freeness results broaden the scope. However, the proof of Theorem 1 as written contains a genuine gap, so the central upper bound is not yet established; the gap appears local and repairable. All results are tied to the paper's specific Definition 2.4, and alternative payment-aware proportionality notions would not automatically inherit these bounds.","major_comments":[{"comment":"The case analysis for A_l = B_l ∪ B_h is incomplete. The text asserts that the only way A_l can become B_l ∪ B_h is the merge in Line 10 at iteration i = l. This is false: if at iteration i = h the merge in Line 10 creates A_h = B_l ∪ B_h and sets A_l = ∅, then at the later iteration i = l the swap in Line 7 can move that union into A_l. The written proof contains no bound on c_l(B_l ∪ B_h) for this path. The gap is repairable: the merge at i = h gives c_h(B_l ∪ B_h) ≤ 3M/2, and the swap at i = l is executed only if c_l(A_h) + c_h(A_l) < c_l(A_l) + c_h(A_h); since A_l = ∅ in this path, that inequality yields c_l(B_l ∪ B_h) < c_h(B_l ∪ B_h) ≤ 3M/2. The proof should include this case explicitly.","section":"Section 4.1, proof of Theorem 1"},{"comment":"The contradiction step in the final case is not written correctly. The displayed inequality c_h(B_l) < c_l(B_l) does not by itself imply that the merge condition in Line 10 was met at iteration i = h; with no prior swap, that condition is c_h(B_h) < c_l(B_h), not c_h(B_l) < c_l(B_l). The intended contradiction does follow, but from the two facts c_h(B_h) ≤ M < 3M/2 < c_l(B_h) and c_h(B_l) ≤ M/2, which together give c_h(B_h) < c_l(B_h) and c_h(B_h) + c_h(B_l) ≤ 3M/2. The proof should be rewritten to state this reasoning explicitly.","section":"Section 4.1, proof of Theorem 1, final case"}],"minor_comments":[{"comment":"In the normalization argument, the text writes c_i([m]) where it should write c_i([n]); additionally, the displayed inequality in the cycle argument contains a self-comparison c_{i_j}(A_{i_j}) < c_{i_j}(A_{i_j}), which should read c_{i_{j+1}}(A_{i_j}) < c_{i_j}(A_{i_j}). The intended argument is clear, but these typos should be fixed.","section":"Section 4.2, proof of Theorem 3"},{"comment":"In the proof of Theorem 4, the average of the values for good m is (m^2 + m + 1)/m = m + 1 + 1/m, not m + 1 as printed. The conclusion is unaffected because this value is still greater than m.","section":"Section 5, proof of Theorem 4"},{"comment":"The phrase 'stronger version of envy-freeness' is misleading: α-cyclic-envy-freeness imposes constraints only between adjacent machines in a cycle, so it is a weaker condition than envy-freeness. The intended statement is that the lower bound is strengthened because it holds even for a weaker fairness notion; the wording should be adjusted.","section":"Section 6, Definition 6.4 and Theorem 9"},{"comment":"The assertion that if A_l = B_h at the end then A_l and A_h were neither swapped nor merged in the iterations with i = l or i = h is stated without justification. It is true, because a swap at i = h would make the reverse swap at i = l impossible (the two swap inequalities are mutually exclusive), and a merge at either iteration would change A_l away from B_h, but the proof should say so.","section":"Section 4.1, proof of Theorem 1"},{"comment":"The termination of Algorithm 2 is not argued. Termination follows because each reallocation strictly decreases the total cost Σ_i c_i(A_i), so the algorithm cannot cycle; this should be stated explicitly.","section":"Section 4.1, Algorithm 2"}],"recommendation":"major_revision","confidential_remarks":"The central gap is real but local: the proof of Theorem 1 omits the swap-after-merge path and the final-case contradiction is imprecisely justified. I believe the 3/2 bound is correct and repairable, and the other results appear sound. The paper should be sent back for a careful revision of Section 4.1 rather than rejected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a good paper with one real hole in the proof of the main theorem. The hole is repairable, and I'd send it to a referee.\n\nThe new question is well posed: with payments, how much does proportionality cost in makespan? The answer, tight 3/2, contrasts sharply with the logarithmic impossibility for envy-freeness. The mean-efficiency characterization (Theorem 6) is elegant and correct. The proof is clean, and the payment formula that realizes any mean-efficient allocation is simple. The lower bound construction is also neat: it forces the allocation to be diagonal, then uses mean-efficiency to contradict the cost sum. The normalized-instance result (Theorem 3) is a nice positive counterpart, and the goods-allocation contrast (Theorems 4 and 5) is useful.\n\nThe main proof, however, is not complete as written. In the analysis of Algorithm 1, the text says the only way A_ell becomes B_ell union B_h is via the merge at i=ell. That is false when h < ell: the merge at i=h can put the union in A_h, and then the swap at i=ell can move it to A_ell. The authors do not bound that path. The gap is easily patched: the merge at i=h gives c_h(union) <= 3/2M, and the later swap at i=ell only fires if c_ell(union) < c_h(union), so the bound follows. But the printed proof does not say this, so Theorem 1 is not established as written.\n\nOne more caveat worth flagging: proportionality here is Definition 2.4, which compares each machine's net cost to the average of its own costs across bundles, not to the costs of other machines. That is a defensible notion, and the paper is explicit about it, but the 3/2 result is tied to it. Switching to the Wu-Zhang-Zhou definition could change things.\n\nAlso, the 3/2 mechanism is existential in poly time: it needs an optimal allocation as input, which is NP-hard. The authors note this and give a poly-time 3-approximation. That is fine, but readers should know the exact claim.\n\nOverall, the paper deserves serious peer review. The theorems are mostly proved cleanly; the one gap is localized and repairable. I would accept after the authors fix the case analysis in Theorem 1.","headline":"Tight 3/2 price of proportionality with payments is new and mostly right, but Theorem 1's proof has a repairable gap that should be fixed before publication.","tokens_in":19996,"tokens_out":7775,"would_cite":true,"duration_ms":67384,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90B35","91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a payment-based proportional schedule can always reach 3/2 of the optimal makespan, and that no proportional mechanism can do better when n ≥ m.","keywords":["job scheduling","unrelated machines","makespan approximation","proportionality","mean efficiency","fair division of chores","mechanism design with payments","egalitarian welfare"],"falsifier":"Take the cost matrix from Theorem 2's proof: entries 1 on the diagonal, 1/2 below the diagonal, and $3/2 - \\epsilon/2$ above the diagonal, with $m = n$. If any proportional mechanism (using Definition 2.4) returns an allocation whose makespan is below $(3/2 - \\epsilon)$, that would falsify the tightness claim; the paper's own argument shows such an allocation would have to be the identity allocation with total cost $m$, violating mean efficiency.","tokens_in":19038,"feed_emoji":"⚖️","tokens_out":7154,"duration_ms":69240,"temperature":0.7,"pith_summary":"This paper asks how much makespan efficiency must be sacrificed when a scheduler also demands fairness toward the machines. Its answer: for the fairness notion of proportionality, the loss is exactly a factor of 3/2 — no more and no less. The positive half is a mechanism, the Anti-Diagonal Mechanism, that converts any schedule into a proportionable one while increasing makespan by at most 3/2. The negative half shows that when there are at least as many jobs as machines, every proportional mechanism must sometimes pay this full factor. The paper also shows that when every machine has the same total cost, a proportional mechanism can achieve the optimal makespan exactly, and it extends these ideas to the dual goods-allocation problem.","feed_headline":"Proportional scheduling hits a tight 3/2 makespan bound","feed_subtitle":"With payments, a proportional schedule can reach 3/2 of optimal makespan, and no fairer guarantee exists.","key_machinery":"The central object is mean efficiency (Definition 3.1), a budget on the total cost of an allocation, proved equivalent to proportionability in Theorem 6 and therefore the exact condition that payments must be able to fix. The main algorithmic engine is the Anti-Diagonal Mechanism (Algorithm 1): it reads any initial allocation, forms the $m \\times m$ matrix of costs of each machine for each initial bundle, and picks the anti-diagonal with minimum total cost; because the average of anti-diagonal totals equals the average of the whole matrix, this choice is mean-efficient. Subsequent swap and merge operations lower the total cost, preserving mean efficiency, while a careful case analysis bounds every machine's final bundle cost by 3/2 times the input makespan. For normalized instances, the mechanism instead takes the makespan-minimizing allocation of minimal total cost and proves mean-efficiency through a directed graph with no cycles.","core_discovery":"The central claim is a tight equivalence between fairness and efficiency. An allocation function is proportionable — meaning it can be paired with payments so that each machine's net cost is at most its average share — if and only if it is mean-efficient: the total cost of the allocation is no larger than the average row cost of the cost matrix times the number of machines. The theorem comes with an explicit payment formula, $p_i = c_i(A_i) - (1/m)c_i([n])$, that realizes proportionality. On top of this characterization sits the Anti-Diagonal Mechanism, which selects a cost-minimizing anti-diagonal of the matrix of machine costs under the initial allocation, then applies swap and merge operations that preserve mean-efficiency while capping makespan at 3/2 of the initial schedule's makespan. For normalized instances the paper shows the cheapest makespan-optimal allocation is mean-efficient, giving an exact proportional mechanism.","pith_inferences":["The 3/2 ratio matches the classic inapproximability threshold for makespan minimization without any fairness constraint, which suggests that in this payment model proportionality may not be the binding obstacle to efficiency.","Because the characterization equates proportionality with an average-cost bound, fair scheduling is effectively a bicriteria problem: fairness is guaranteed as soon as total cost is controlled, so future work can focus on allocations that simultaneously control makespan and average cost.","The exactness for normalized instances hints that settings with comparable total costs may be qualitatively easier for fair mechanisms; a natural test is whether other fairness relaxations, such as EF1 or EFX with payments, also become constant-factor or exact in that regime.","The lower-bound instance is highly structured, almost a triangular matrix; exploring perturbations of it could show whether 3/2 is stable or an artifact of extreme cost asymmetry."],"forward_implications":["The price of proportionality for makespan is exactly 3/2: Theorem 1's mechanism achieves it and Theorem 2's instance rules out any $(3/2 - \\epsilon)$-approximation when $n \\ge m$.","Feeding the Anti-Diagonal Mechanism with the polynomial-time 2-approximation of [37] yields a polynomial-time proportional mechanism with a 3-approximation to the optimal makespan.","Under normalized costs, proportionality costs nothing in efficiency: a proportional mechanism attains the optimal makespan, while envy-free mechanisms still incur a logarithmic loss.","For the goods-allocation counterpart (maximizing egalitarian welfare), no proportional mechanism can guarantee any finite approximation in general, but normalized instances admit an exact proportional mechanism.","The cyclic lower-bound technique behind the envy-free impossibility does not extend to approximate envy-freeness: for every $\\epsilon > 0$ there is a $(1-\\epsilon)$-cyclic-envy-free mechanism with $1/\\epsilon$ makespan approximation."],"supporting_citations":[{"why":"Supplies the baseline optimal-makespan benchmark and the polynomial-time 2-approximation algorithm that yields a polynomial-time proportional mechanism.","marker":"[37]"},{"why":"Establishes the logarithmic envy-free lower bound that motivates the paper's contrast; its proof technique is analyzed in Section 6.","marker":"[23]"},{"why":"Provides the local-efficiency characterization of envy-freeable allocations, which the paper adapts to approximate envy-freeness.","marker":"[33]"},{"why":"Defines an alternative proportionality notion without payments, which the paper explicitly sets its own Definition 2.4 against.","marker":"[46]"},{"why":"Gives the original characterization of envy-freeable allocations that underlies the comparison in Theorem 7.","marker":"[3]"}],"fun_headline_variants":["Tight 3/2 makespan with proportional fairness and payments","Proportional mechanisms: tight 3/2 makespan approximation","Fairness with payments: makespan within 1.5x, tight","Tight 3/2: proportional mechanisms with payments beat envy-free","Exact makespan for normalized costs via proportional mechanisms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole result rests on Definition 2.4's notion of proportionality, where machine i's fair share is computed from i's own costs minus the average payment; if one uses another definition of proportional fairness, the 3/2 bound is not shown to hold.","fun_headline_variants_meta":{"raw":{"variants":["Tight 3/2 makespan with proportional fairness and payments","Proportional mechanisms: tight 3/2 makespan approximation","Fairness with payments: makespan within 1.5x, tight","Tight 3/2: proportional mechanisms with payments beat envy-free","Exact makespan for normalized costs via proportional mechanisms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000948,"raw_usage":{"total_tokens":4048,"prompt_tokens":945,"completion_tokens":3103,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":3013}},"tokens_in":561,"tokens_out":3103,"duration_ms":22031,"temperature":1.0,"reasoning_tokens":3013,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:46:33.518076+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the cost matrix from Theorem 2's proof: entries 1 on the diagonal, 1/2 below the diagonal, and $3/2 - \\epsilon/2$ above the diagonal, with $m = n$. If any proportional mechanism (using Definition 2.4) returns an allocation whose makespan is below $(3/2 - \\epsilon)$, that would falsify the tightness claim; the paper's own argument shows such an allocation would have to be the identity allocation with total cost $m$, violating mean efficiency.","supporting_citations":[{"cited_title":"Appro ximation algorithms for scheduling unre- lated parallel machines","cited_arxiv_id":null,"evidence_quote":"Supplies the baseline optimal-makespan benchmark and the polynomial-time 2-approximation algorithm that yields a polynomial-time proportional mechanism."},{"cited_title":"Envy-free makespan approximation","cited_arxiv_id":null,"evidence_quote":"Establishes the logarithmic envy-free lower bound that motivates the paper's contrast; its proof technique is analyzed in Section 6."},{"cited_title":"Multi-dimensional envy-free scheduling mechanisms","cited_arxiv_id":null,"evidence_quote":"Provides the local-efficiency characterization of envy-freeable allocations, which the paper adapts to approximate envy-freeness."},{"cited_title":"One quarter e ach (on average) ensures proportionality","cited_arxiv_id":null,"evidence_quote":"Defines an alternative proportionality notion without payments, which the paper explicitly sets its own Definition 2.4 against."},{"cited_title":"A derivation of the money rawlsian s olution","cited_arxiv_id":null,"evidence_quote":"Gives the original characterization of envy-freeable allocations that underlies the comparison in Theorem 7."}],"review_version":1}