Fair Division with Bounded Sharing: Binary and Non-degenerate Valuations (d4-conf-sagt-2024-0002)

Given two complete agent types of masses \(\mu_1=\mu_2=1/2\), \(m\) object classes each supplied with mass \(1/2\), and non-negative rational additive values \(v_{i,o}\), decide whether the object classes can be partitioned into integral bundles \(B_1,B_2\) such that \(u_i(B_i)\geq \frac{1}{2}\sum_o v_{i,o}\) for both types. Equivalently, decide whether a zero-aggregate-sharing high-multiplicity allocation exists, which for two bundles is also envy-free.

There are two complete agent types, each of mass \(1/2\), and \(m\) object classes, each supplied with mass \(1/2\). The input gives non-negative rational additive values \(v_{i,o}\) for each type \(i\) and class \(o\). An integral partition \((B_1,B_2)\) assigns every class wholly to one type, with \(u_i(B_i)=\sum_{o\in B_i}v_{i,o}\).

Is deciding whether an integral partition with \(u_i(B_i)\geq \frac12\sum_o v_{i,o}\) for both types solvable in polynomial time, or is it NP-hard?

For two discrete agents, deciding whether a proportional allocation with zero sharing exists is NP-hard, even for non-degenerate valuations. No result for the exact mass formulation was verified.

Result

The stated decision problem is \(\mathrm{NP}\)-complete under binary encoding of the rational values, even when both types have identical positive integer valuations.

Reduction from PARTITION

We use the standard \(\mathrm{NP}\)-complete problem PARTITION: given positive integers \(a_1,\ldots,a_m\) encoded in binary, decide whether some subset \(S\subseteq\{1,\ldots,m\}\) satisfies \(\sum_{o\in S}a_o=\frac12\sum_{o=1}^{m}a_o\). See the [number-partitioning reference](https://www.sciencedirect.com/science/article/pii/S0004370298000861).

Given such an instance, create the two types and the object classes with exactly the prescribed masses: each type and each class has mass \(1/2\). Set \(v_{1,o}=v_{2,o}=a_o\) for every class \(o\). This construction copies each input integer twice and therefore takes polynomial time. Its valuations satisfy all the stated hypotheses.

Write \(A=\sum_{o=1}^{m}a_o\). For any integral partition \((B_1,B_2)\), put \(x=\sum_{o\in B_1}a_o\). Because every class belongs to exactly one bundle, the utilities are \(u_1(B_1)=x\) and \(u_2(B_2)=A-x\). Thus the required inequalities are precisely \(x\geq A/2\) and \(A-x\geq A/2\). The second inequality gives \(x\leq A/2\), so together they are equivalent to \(x=A/2\).

Consequently:

• If the PARTITION instance has a solution \(S\), assigning \(B_1=S\) and \(B_2=\{1,\ldots,m\}\setminus S\) gives both types utility \(A/2\).
• If the constructed allocation instance has a feasible integral partition, its bundle \(B_1\) has sum exactly \(A/2\), and hence solves PARTITION.

This proves a polynomial-time many-one reduction and establishes \(\mathrm{NP}\)-hardness.

Membership in \(\mathrm{NP}\)

A certificate specifies, for each class, which type receives it. Its length is \(m\) bits.

To verify it, compute each type’s bundle value and total value and check \(2\sum_{o\in B_i}v_{i,o}\geq\sum_{o=1}^{m}v_{i,o}\).

These comparisons admit exact polynomial-time arithmetic. Specifically, write \(v_{i,o}=p_{i,o}/q_{i,o}\), with integer \(p_{i,o}\geq0\) and integer \(q_{i,o}>0\), and multiply each type’s inequality by \(D_i=\prod_{o=1}^{m}q_{i,o}\). The bit length of \(D_i\) is at most the sum of the denominators’ bit lengths, up to a constant. The resulting integer sums also have polynomial bit length, so verification takes polynomial time.

The problem therefore belongs to \(\mathrm{NP}\).

Applicability to the mass formulation

The reduction uses the exact masses specified in the question and the stated utility formula \(u_i(B_i)=\sum_{o\in B_i}v_{i,o}\). No additional cardinality or bundle-mass constraint is imposed by that definition. Thus the reduction directly settles the mass formulation without transferring a theorem about discrete agents.

Identical valuations are permitted by the input hypotheses. A further requirement of non-degeneracy would be a separate restriction; it is unnecessary for the question asked.

⟨structured verdict parsed — rendered above⟩

The proof is correct and fully resolves USER_TASK under binary encoding. No major or minor issues were found.

• Source problem and hypotheses. The prover precisely states the positive-integer, binary-encoded decision version of PARTITION, whose NP-completeness is standard and consistent with the [cited reference](https://www.sciencedirect.com/science/article/pii/S0004370298000861). No restriction required by that source problem is lost in the reduction.

• Construction and encoding size. Setting \(v_{1,o}=v_{2,o}=a_o\) produces admissible positive integer valuations. There are exactly two types, and every type and object class receives the prescribed mass \(1/2\). Copying the input integers twice and specifying these constant masses requires polynomial output length and time.

• Utility calculation. Since the bundles form a partition of all classes, \(u_1(B_1)=x\) and \(u_2(B_2)=A-x\) follow exactly from the stated additive utility definition. Both types’ total values equal \(A\).

• Equivalence of feasibility and equal partition. The inequalities \(x\geq A/2\) and \(A-x\geq A/2\) hold simultaneously exactly when \(x=A/2\). Both directions of the many-one reduction are explicitly established: a solution subset yields a feasible allocation, and a feasible allocation yields a solution subset. There is no missing existential or universal quantifier.

• Boundary cases. An odd total \(A\) causes no difficulty: an integer subset sum cannot equal \(A/2\), so both instances are infeasible. Empty bundles are covered by the same utility equations. Zero valuations are permitted in the target problem but need not occur in a hardness reduction. They also cause no difficulty for the proposed verifier. If an empty class set is allowed, its zero sums satisfy both inequalities.

• Membership in NP. An \(m\)-bit assignment certificate specifies a complete integral partition. Clearing denominators preserves the inequalities because every denominator is positive. The product \(D_i\) has polynomial bit length; multiplying numerators by the corresponding integer factors and summing at most \(m\) terms also yields polynomial bit length. The required products, exact divisions, additions, and comparisons take polynomial time. Reduced fractions are unnecessary.

• Applicability to the stated mass formulation. USER_TASK explicitly defines utilities as sums over assigned classes and imposes no bundle-mass or cardinality constraint. The proof therefore uses the specified formulation directly. It neither assumes nor needs a result about discrete-agent allocations. Non-degeneracy is mentioned only as background in USER_TASK, not required of the input.

The argument establishes NP-completeness, including NP-hardness for identical positive integer valuations. It does not claim strong NP-hardness or establish hardness under an additional non-degeneracy restriction. No repair or clarification is required.

⟨structured verdict parsed — rendered above⟩