Maximin Share Allocations on Cycles (d4-conf-ijcai-2018-0657)

Given a finite goods set \(V\), a complete compatibility graph, a nonnegative rational additive utility \(u\), a rational threshold \(k\), and population mass \(1\) with per-capita supply \(\sigma_v=\frac12\) for every \(v\in V\), decide whether variables \(x_B\ge0\), for \(B\subseteq V\), exist such that \(\sum_{B\subseteq V}x_B=1\), \(\sum_{B\ni v}x_B=\frac12\) for every \(v\in V\), and \(x_B>0\Rightarrow u(B)=\sum_{v\in B}u(v)\ge k\). Each positive \(x_B\) is mass receiving the integral bundle \(B\), with at most one copy of each good type per bundle.

Given a nonempty goods set \(V\), with \(m=|V|\), a complete compatibility graph, utilities \(u(v)\in\mathbb{Q}_{\geq0}\), and a threshold \(k\in\mathbb{Q}_{\geq0}\), consider a population of total mass \(1\) sharing utility \(u\). Every subset \(B\subseteq V\), including the empty set, is an admissible integral bundle, containing at most one copy of each good; its utility is \(u(B)=\sum_{v\in B}u(v)\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau=1\), with mass \(1\); \(\tau\) denotes support size, not the number of possible types. Let \(L\) be the total binary input bit length; state running times in \(m,\tau,L\).
Each good has per-capita supply \(\sigma_v=\frac12\). Feasibility means that real masses \(x_B\geq0\), indexed implicitly by all \(B\subseteq V\), satisfy \(\sum_{B\subseteq V}x_B=1\), \(\sum_{B\ni v}x_B=\frac12\) for every \(v\in V\), and \(x_B>0\Rightarrow u(B)\geq k\). Each positive \(x_B\) is population mass receiving bundle \(B\).

Is this feasibility problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

The discrete problem of partitioning all goods into two bundles each worth at least \(k\) is NP-complete, even with a complete compatibility graph and nonnegative integer utilities ([source](https://arxiv.org/html/1905.03038v2)). No result settling exactly the continuous feasibility problem above was identified in the literature search.

Result

The problem is \(\mathrm{NP}\)-complete, already with \(\tau=1\) and nonnegative integer utilities. Thus a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

In fact, continuous feasibility is equivalent to partitioning the goods into two bundles each worth at least \(k\).

Exact equivalence

Write \(U=u(V)=\sum_{v\in V}u(v)\).

Proposition. A feasible mass distribution exists if and only if there is a subset \(B\subseteq V\) such that \(u(B)\geq k\) and \(u(V\setminus B)\geq k\).

Proof. Suppose first that \((x_B)_{B\subseteq V}\) is feasible. Additivity and the supply equalities give

\(\displaystyle \sum_{B\subseteq V}x_Bu(B)=\sum_{v\in V}u(v)\sum_{B\ni v}x_B=\frac12\sum_{v\in V}u(v)=\frac U2.\)

Every bundle with positive mass has utility at least \(k\), and the masses sum to \(1\). Consequently \(U/2\geq k\).

The support is nonempty and finite because there are only \(2^m\) bundles. There must therefore be a supported bundle \(B_0\) with \(u(B_0)\leq U/2\): otherwise the weighted average above would exceed \(U/2\). Since \(B_0\) is supported,

\(\displaystyle k\leq u(B_0)\leq \frac U2.\)

Its complement satisfies

\(\displaystyle u(V\setminus B_0)=U-u(B_0)\geq \frac U2\geq k.\)

Thus \(B_0\) and its complement constitute the required partition.

Conversely, suppose \(B\) and \(V\setminus B\) both have utility at least \(k\). Assign mass \(1/2\) to each and zero to every other bundle. These two bundles are distinct because \(V\neq\varnothing\). The masses sum to \(1\), and every good occurs in exactly one of them, so its assigned mass is exactly \(1/2\). Both bundles meet the threshold and are admissible. This distribution is feasible. \(\square\)

In particular, whenever a feasible distribution exists, one exists using exactly two complementary bundles with rational masses \(1/2\). Allowing arbitrary real masses introduces no additional feasible instances.

Hardness

Reduce from the standard \(\mathrm{NP}\)-complete problem PARTITION: given a nonempty list of positive binary integers \(a_1,\ldots,a_m\), determine whether some subset sums to half their total. This is also the source problem used in [Proposition 3.1 of the supplied paper](https://arxiv.org/html/1905.03038v2).

Construct one good \(v_i\) for each integer, and set

\(\displaystyle u(v_i)=a_i,\qquad S=\sum_{i=1}^{m}a_i,\qquad k=\frac S2.\)

Use a complete compatibility graph, one utility type of mass \(1\), and supply \(1/2\) for every good.

By the proposition, this instance is feasible exactly when some \(B\subseteq V\) satisfies

\(\displaystyle u(B)\geq \frac S2,\qquad S-u(B)\geq \frac S2.\)

Together these inequalities are equivalent to \(u(B)=S/2\), precisely the PARTITION condition. This also handles odd \(S\): no integer-valued subset can attain \(S/2\).

The transformation has polynomial output length. Using ordinary binary arithmetic, it can be implemented in \(O(mL^2+m^2)\) bit operations, where \(L\) is the constructed instance’s total bit length; the \(m^2\) term accommodates an explicitly written adjacency matrix. Throughout the reduction, \(\tau=1\). Hence the problem is \(\mathrm{NP}\)-hard under the stated restrictions.

Membership and running times

By the proposition, a certificate is just the \(m\)-bit incidence vector of a subset \(B\). The verifier computes \(u(B)\) and \(u(V\setminus B)\) exactly and compares both with \(k\).

For binary rational inputs of total length \(L\), these calculations admit \(O(L)\)-bit intermediate numerators and denominators: products of input denominators have bit length bounded by their total encoded length, and summing at most \(m\) terms adds only \(O(\log m)\) bits. Schoolbook arithmetic therefore gives verification time \(O(mL^2)\), polynomial in \(m,\tau,L\) with \(\tau=1\).

Thus the problem belongs to \(\mathrm{NP}\), completing the \(\mathrm{NP}\)-completeness proof. Enumerating all subsets also gives an exact deterministic algorithm taking \(O(2^m mL^2)\) bit operations.

⟨structured verdict parsed — rendered above⟩

The prover’s argument is correct and resolves the continuous feasibility problem. It establishes NP-completeness under the stated binary encoding, already with \(\tau=1\) and nonnegative integer utilities. No major or minor mathematical issues were found.

• Expected utility identity. The equality

\(\sum_{B\subseteq V}x_Bu(B)=U/2\)
follows directly from additivity and the supply equalities. All sums are finite, so exchanging their order is valid even when the masses are arbitrary real numbers.

• Necessary threshold bound. Every positive-mass bundle has utility at least \(k\), and the masses sum to \(1\). Therefore their weighted average is at least \(k\), giving \(U/2\geq k\). This step uses exactly the feasibility conditions.

• Selection of a supported bundle. The support is nonempty because the masses sum to \(1\), and finite because there are only \(2^m\) subsets. If every supported bundle had utility strictly greater than \(U/2\), its weighted average would also be strictly greater than \(U/2\). Thus the asserted bundle \(B_0\) exists and satisfies \(k\leq u(B_0)\leq U/2\).

• Complement meets the threshold. Additivity gives

\(u(V\setminus B_0)=U-u(B_0)\geq U/2\geq k\).
The complement is admissible because the task permits every subset. This proves the forward implication without assuming that the original distribution contains complementary bundles.

• Converse construction. Assigning mass \(1/2\) to a qualifying subset and its complement satisfies normalization, every supply equality, and the utility restriction. These bundles are distinct because \(V\neq\varnothing\). The claim that every feasible instance admits exactly two complementary positive-mass bundles is therefore justified.

• Boundary cases. The argument remains valid for \(k=0\), zero-valued goods, \(U=0\), and \(m=1\). Empty bundles are expressly admissible. When \(U/2<k\), the expected utility identity correctly rules out feasibility. No omitted boundary case invalidates either implication.

• Hardness reduction. The prover precisely states the binary-integer PARTITION problem used as its source. Its construction satisfies all target restrictions, including one supported type of mass \(1\). The two inequalities at threshold \(S/2\) force equality with \(S/2\), so both directions of the reduction hold. Odd totals correctly produce infeasible instances. The attribution to PARTITION as the source of the paper’s Proposition 3.1 is accurate; that proposition also treats complete graphs and integer utilities. [Supplied paper, Proposition 3.1](https://arxiv.org/html/1905.03038v2#S3)

• Reduction size and running time. Computing \(S\) and encoding \(S/2\) require polynomially many bits in the source input length. An explicit complete-graph adjacency matrix adds \(O(m^2)\) bits. Consequently, the stated \(O(mL^2+m^2)\) construction bound, with \(L\) denoting the constructed instance length, is a valid conservative polynomial bound.

• NP membership. The equivalence supplies an \(m\)-bit subset certificate for every feasible instance. Checking both bundle utilities suffices, so the verifier does not need to encode or certify arbitrary real masses. Products of input denominators have bit length bounded by their total input length; numerator growth from summation adds at most \(O(\log m)\) bits. Since the explicit utility list ensures \(m=O(L)\), the asserted \(O(L)\)-bit intermediates and \(O(mL^2)\) verification bound are valid.

• Final complexity claims. NP-hardness and NP membership together establish NP-completeness. The deterministic enumeration bound \(O(2^m mL^2)\) follows from checking every subset. The dependence on \(\tau\) is correctly handled by its fixed value \(\tau=1\).

No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩