Pith. sign in

REVIEW 2 major objections 4 minor 11 references

For agents with one of two utility functions, the paper gives a 2-approximation for maximizing social welfare among EF1 allocations, and tight ratios for three agents.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-04 18:46 UTC pith:AWRJLCF3

load-bearing objection Real algorithmic improvements for USW-EF1 with two agent types, but the three-agent unnormalized proof has a genuine missing edge case: it assumes the optimal allocation gives agent 1 at least one item. the 2 major comments →

arxiv 2509.09641 v1 pith:AWRJLCF3 submitted 2025-09-11 cs.GT cs.DS

Maximizing social welfare among EF1 allocations at the presence of two types of agents

Jiaxuan Ma , Yong Chen , Guangting Chen , Mingyang Gong , Guohui Lin , An Zhang This is my paper
classification cs.GT cs.DS MSC 68W2591B32
keywords fair allocationEF1utilitarian social welfaretwo types of agentsapproximation algorithmitem preference ordercritical setenvy-cycle elimination
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper studies the fair-division problem in which indivisible items must be allocated to agents, the allocation must be envy-free up to one item (EF1), and the goal is to maximize total utility across all agents. It focuses on the special case where every agent's utilities come from one of only two shared utility functions ('two types'). The authors prove that for normalized utilities, a simple algorithm based on sorting items by the preference ratio u1/u3 achieves a 2-approximation for any number of agents, improving the previous 16√n bound. For three agents, they give a tight 5/3-approximation when utilities are normalized and a best-possible tight 2-approximation when they are unnormalized. Together these match known lower bounds, settling the approximability for these cases.

Core claim

On the paper's own terms, the central claim is that in the two-type setting the maximum utilitarian social welfare among EF1 allocations can be approximated within constant factors that are tight for three agents. The key structural idea is the item preference order ρ(g)=u1(g)/u3(g): in an efficient allocation, items with high ratio should go to the first type and those with low ratio to the second. Algorithms Approx1, Approx10, and Approx11 maintain 'good' allocations—where every first-type bundle precedes every second-type bundle in this order—and use this property to guarantee EF1. For the three-agent unnormalized case, a 'critical set' K built from the preference order yields the bound O

What carries the argument

The item preference order (ratio u1/u3 per item, sorted non-increasingly) and the derived notion of a 'good' allocation (first-type bundles precede second-type bundles in this order) form the backbone of all three algorithms. For the three-agent unnormalized case, the 'critical set' K—a prefix of the preference order satisfying three conditions—yields the bound OPT ≤ u1(K)+u3(M\K), which is then used to certify the 2-approximation. Round-robin and envy-cycle elimination are used as subroutines to complete partial EF1 allocations.

Load-bearing premise

The three-agent unnormalized proof requires that in some fixed optimal EF1 allocation A*, the first-type agent receives at least one item, so that the critical item g* = arg max_{g in A*_1} u3(g) exists; if every optimal allocation gives this agent nothing, the bound OPT ≤ u1(K)+u3(M\K) is not derived and the 2-approximation is unsupported.

What would settle it

Construct a three-agent instance with two unnormalized utility functions in which every optimal EF1 allocation assigns an empty bundle to agent 1. Run the combination of Approx3/Approx7/Approx9 and compute SOL and OPT; if SOL < OPT/2, the claimed tight 2-approximation is false. Equivalently, a concrete instance where the inequality of Lemma 4 fails for such an optimal allocation would settle it.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • For any number of agents with two normalized utility functions, USW-EF1 is APX-complete, because the new 2-approximation combines with existing APX-hardness.
  • For three agents with two unnormalized utility functions, the approximation ratio cannot be better than 2 unless P=NP, and the paper's algorithm achieves exactly 2.
  • For three agents with normalized utilities, the optimal approximation ratio is exactly 5/3.
  • The preference-order design principle can be reused in other fair-division problems with a small number of utility functions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the methods extend to arbitrary counts n1,n2 per type, the approximation ratio may become a function of the type counts rather than the total number of agents—the authors explicitly leave this gap open.
  • The tightness instances use only five items, suggesting the hardness arises from preference-order interactions, not instance size; stress-testing on random two-type instances might reveal whether average-case performance is much better than worst-case.
  • The 'good allocation' idea could transfer to other fairness notions (e.g., EFX) in two-type settings, as keeping bundles separated by preference ratio may make EF1 easier to maintain.

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

2 major / 4 minor

Summary. The paper studies the problem of maximizing utilitarian social welfare among EF1 allocations when there are only two additive utility types. Section 2 gives a 2-approximation for normalized utilities for any number of agents (Approx1), improving the previous 16√n bound. Section 3 treats three agents with unnormalized utilities: it defines a critical set K for the item g* in an optimal EF1 allocation, proves an upper bound on OPT via Lemma 4, and presents three algorithms (Approx3, Approx7, Approx9) for the three cases of the critical set, claiming a tight 2-approximation. Section 4 gives two algorithms (Approx10, Approx11) for three agents with normalized utilities and claims a tight 5/3-approximation. The paper includes tightness instances for both three-agent results.

Significance. If the proofs are correct, the results are significant: they replace the earlier 16√n approximation by a constant 2 for the normalized two-type case, confirm APX-completeness of that case, and provide tight approximation bounds for three agents. The algorithmic ideas are elementary and clearly presented, and the paper provides explicit tightness examples. However, two gaps in Section 3—the possible non-existence of g* and an invalid algebraic step involving zero u3 values—mean that the central 2-approximation theorem for three unnormalized agents is not established as written. These gaps are load-bearing but appear repairable, so the contribution is promising rather than conclusively wrong.

major comments (2)
  1. [§3, Definition 3/Lemma 4] The proof assumes an optimal EF1 allocation A* with A*_1 nonempty, because g* = arg max_{g in A*_1} u3(g) is used in Lemmas 3 and 4 and in Theorems 2–4. No separate argument is given for the case A*_1 = ∅. This case is real: let u1 ≡ 0, M = {g,h}, u3(g)=100, u3(h)=1. Then every optimal EF1 allocation gives both items to agents 2 and 3, so A*_1 is empty in every optimal allocation. The claimed 2-approximation for three unnormalized agents is therefore not established in this case. A short separate argument (u1≡0 implies running round-robin on agents 2 and 3 achieves OPT) would repair the gap.
  2. [§3, Lemma 4/Eq. (2)] The proof uses ρ(S)=u1(S)/u3(S) and the identity u3(S)(ρ(S)-1)=u1(S)-u3(S). This identity is invalid when u3(S)=0 and u1(S)>0. This is not vacuous: let M={b,a} with u1(b)=20,u3(b)=0, u1(a)=10,u3(a)=1. The allocation A*=({a,b},∅,∅) is optimal and EF1; for g*=a, Algorithm 2 returns K={a}, and Definition 3 is satisfied, but Lemma 4 would give OPT≤u1(K)+u3(M\K)=10, while OPT=30. Hence Lemma 4 is false as stated, and the proof of Theorems 2–4 is unsound for instances with zero u3 values. The proof must handle zero-utility items explicitly or justify a w.l.o.g. exclusion, which is not given.
minor comments (4)
  1. [§2, Definition 1] The text says the items are given in 'non-decreasing preference order' but then defines ρ(g1)≥ρ(g2)≥...; this should be 'non-increasing'.
  2. [§3.5, tightness table] The values in the tightness instance are garbled in the typesetting: the row for a1 should read 'ϵ, 1, 1, 0, 0' and the row for a2,a3 should read '0, ϵ, 2ϵ, ϵ, ϵ'. Please fix the table.
  3. [§2, Definition 2] The treatment of empty sets is informal ('preference of an empty set is ±∞'). It would be clearer to state explicitly that A≺B holds vacuously when A⊆B, since this convention is relied on in Lemma 6 and elsewhere.
  4. [§1.1/§5] The APX-completeness statement should explicitly note that the cited lower bound 4n/(3n+1) is larger than 1 for every fixed n≥3; a constant approximation ratio alone does not imply APX-completeness without such a lower bound.

Circularity Check

0 steps flagged

No material circularity: the approximation guarantees are proved by direct inequalities from explicit algorithmic invariants, not by assuming the target result.

full rationale

The paper's main results are constructive approximation analyses. Theorem 1 bounds OPT by u1(M)+u3(M)=2 under normalization and then proves SOL>=1 from the 'good allocation' invariant established in Lemma 2 by induction from the algorithm's own item-order assignments; neither bound is assumed from the conclusion. Theorems 2-4 prove SOL >= (1/2)u1(K)+(1/2)u3(M\K) for the algorithm's output and then bound OPT via Lemma 4. Lemma 4 is an analytic inequality derived from the EF1 property of a fixed optimal allocation and from the critical-set conditions; it is not a restatement of the algorithm's output. Crucially, Algo2 enumerates every possible item and constructs a critical set for each, so the algorithm does not need to know g* in advance, and the proof that the best enumerated candidate attains the 2-approximation is a standard 'guess the critical item' argument. Theorems 5-6 similarly derive OPT bounds from normalization and prove SOL lower bounds from the loop invariants and the envy-cycle-elimination property. The only external results cited ([4], [6]) are hardness/lower-bound results by different author groups, used as benchmarks rather than as load-bearing support for the upper bounds. There is a genuine proof gap in Section 3 when the chosen optimal EF1 allocation A* gives agent 1 no items, because then g* is undefined and Lemmas 3-4 do not apply; however this is an unproved case, not circular derivation. No fitted parameter is renamed as a prediction, and no central claim reduces to its own definition.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

No free parameters are fitted: the algorithms use only the sorted preference order and simple min/max selections. The only external inputs are the cited hardness results. No new entities are postulated.

axioms (4)
  • domain assumption Utility functions are additive and non-negative over items
    Standard fair division model, stated in Section 1.
  • domain assumption Items are sorted by non-increasing preference ratio rho(g)=u1(g)/un(g)
    W.l.o.g. ordering used in all algorithms (Section 2, Algorithm 1).
  • domain assumption The lower bounds from Bu et al. [6] apply to the two-types special case
    Used to conclude APX-completeness and to claim the 2-approximation for three unnormalized agents is best possible.
  • standard math EF1 can be verified by pairwise envy after removing one item
    Definition given in Section 1.

pith-pipeline@v1.3.0-alltime-deepseek · 24624 in / 25728 out tokens · 237400 ms · 2026-08-04T18:46:03.259099+00:00 · methodology

0 comments
read the original abstract

We study the fair allocation of indivisible items to $n$ agents to maximize the utilitarian social welfare, where the fairness criterion is envy-free up to one item and there are only two different utility functions shared by the agents. We present a $2$-approximation algorithm when the two utility functions are normalized, improving the previous best ratio of $16 \sqrt{n}$ shown for general normalized utility functions; thus this constant ratio approximation algorithm confirms the APX-completeness in this special case previously shown APX-hard. When there are only three agents, i.e., $n = 3$, the previous best ratio is $3$ shown for general utility functions, and we present an improved and tight $\frac 53$-approximation algorithm when the two utility functions are normalized, and a best possible and tight $2$-approximation algorithm when the two utility functions are unnormalized.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

11 extracted references

  1. [1]

    Amanatidis, H

    G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu. Fair division of indivisible goods: Recent progress and open questions.Artificial Intelligence, 322:Article 103965, 2023. Efficient EF1 allocation for two types of agents (v: September 21, 2025)20

    2023

  2. [2]

    Amanatidis, G

    G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, and A. Voudouris. Fair division of indivisible goods: A survey. InProceedings of IJCAI 2022, pages 5385–5393, 2022

    2022

  3. [3]

    H. Aziz, X. Huang, N. Mattei, and E. Segal-Halevi. Computing welfare-maximizing fair allocations of indivisible goods.European Journal of Operational Research, 307:773–784, 2023

    2023

  4. [4]

    Barman, U

    S. Barman, U. Bhaskar, and N. Shah. Optimal bounds on the price of fairness for indivisible goods. In Proceedings of WINE 2020, pages 356–369, 2020

    2020

  5. [5]

    X. Bei, X. Lu, P. Manurangesi, and W. Suksompong. The price of fairness for indivisible goods.Theory of Computing Systems, 65:1069–1093, 2021

    2021

  6. [6]

    X. Bu, Z. Li, S. Liu, J. Song, and B. Tao. Approximability landscape of welfare maximization within fair allocations. InProceedings of EC 2025, pages 412–440, 2025

    2025

  7. [7]

    E. Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy, 119:1061–1103, 2011

    2011

  8. [8]

    Caragiannis, D

    I. Caragiannis, D. Kurokawa, H. Moulin, A. Procaccia, N. Shah, and J. Wang. The unreasonable fairness of maximum Nash welfare.ACM Transactions on Economics and Computation, 7:12:1–12:32, 2019

    2019

  9. [9]

    Lipton, E

    R. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. InProceedings of EC 2004, pages 125–131, 2004

    2004

  10. [10]

    Steinhaus

    H. Steinhaus. Sur la division pragmatique.Econometrica, 17:315–319, 1949

    1949

  11. [11]

    H. Varian. Equity, envy and efficiency.Journal of Economic Theory, 9:63–91, 1974

    1974