d4-conf-atal-2021-0250 (d4-conf-atal-2021-0250)

Given a finite project set \(P\), supported voter types \(\Pi_1,\ldots,\Pi_\tau\) that are partitions of \(P\), positive rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\), and a rational threshold \(q\), does there exist a partition \(S\) of \(P\) such that \(\sum_{i=1}^{\tau}\mu_i\,|\{A\in\Pi_i:A\in S\}|\ge q\)? Equivalently, find a partition \(S\) maximizing this mass-weighted total complementarity utility.

Given a finite project set \(P\) with \(m\ge 1\), a society is given by its support: an explicit list of \(\tau\ge 1\) distinct partition types \(\Pi_1,\ldots,\Pi_\tau\), each with positive binary rational mass \(\mu_i\), where \(\sum_{i=1}^{\tau}\mu_i=1\). Here \(\tau\) is the support size, not the number of possible partition types. Let \(L\) be the total bit length of the input, including a binary rational threshold \(q\in\mathbb{Q}\).
For an output partition \(S\) of \(P\), type \(i\) has complementarity utility \(u_i(S)=|\{A\in\Pi_i:A\in S\}|\): only exact block matches count. Any partition of \(P\) is admissible, including partitions containing blocks absent from every supported type.
The decision problem asks whether some \(S\) satisfies \(\sum_{i=1}^{\tau}\mu_i u_i(S)\ge q\). State running times in \(m,\tau,L\).

Is this mass-weighted complementarity partition aggregation decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For a finite list of voters with unweighted total complementarity utility, the corresponding decision problem is NP-hard. [Source](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p665.pdf)
No result explicitly treating this normalized rational-mass formulation was located in the literature search.

Result

The decision problem is \(\mathrm{NP}\)-complete under polynomial-time many-one reductions. Thus it has no algorithm polynomial in \(m,\tau,L\) unless \(\mathrm{P}=\mathrm{NP}\).

The normalization of masses does not remove hardness: repeated voters can be compressed into distinct partition types, with their multiplicities represented by rational masses.

Reduction from unweighted complementarity aggregation

We use the following known result: given a project set \(P\), an explicit list of voter partitions \(R_1,\ldots,R_n\), and an integer threshold \(K\), deciding whether a partition \(S\) satisfies
\(\sum_{j=1}^{n}|\{A\in R_j:A\in S\}|\ge K\)
is \(\mathrm{NP}\)-hard. The utility is precisely the exact-block-match utility in the question, and the output may be any partition of \(P\). This is Total-COMP in Definition 2.3 and Section 4.1, with hardness established by Theorem 4.2 of [Jain, Talmon, and Bulteau (2021)](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p665.pdf).

Take such an instance with \(n\ge 1\). Group identical voter partitions. Let \(\Pi_1,\ldots,\Pi_\tau\) be the resulting distinct types, and let \(c_i\) denote the number of voters whose partition equals \(\Pi_i\). Define
\(\mu_i=c_i/n\) and \(q=K/n\).

This gives a valid instance of the requested formulation:

• Each \(\mu_i\) is a positive rational number.
• The supported partitions are distinct, and \(\tau\le n\).
• Because \(\sum_{i=1}^{\tau}c_i=n\), the masses sum to one.
• The project set and the admissible output partitions are unchanged.

For every partition \(S\) of \(P\), grouping the identical summands gives
\[ \sum_{i=1}^{\tau}\mu_i u_i(S) = \frac{1}{n}\sum_{i=1}^{\tau}c_i|\{A\in\Pi_i:A\in S\}| = \frac{1}{n}\sum_{j=1}^{n}|\{A\in R_j:A\in S\}|. \]
Since \(n>0\), this proves the equivalence
\[ \sum_{i=1}^{\tau}\mu_i u_i(S)\ge q \quad\Longleftrightarrow\quad \sum_{j=1}^{n}|\{A\in R_j:A\in S\}|\ge K. \]
Consequently, the original instance is a yes-instance exactly when the constructed instance is a yes-instance. This equivalence includes outputs containing unsupported blocks.

The construction has polynomial bit complexity. Canonically representing each partition by its project-to-block labels allows identical types to be grouped in polynomial time. Each mass \(c_i/n\) requires \(O(\log(n+1))\) bits, and \(K/n\) requires \(O(\log(|K|+1)+\log(n+1))\) bits. Thus the output length is polynomial in the original explicit input length. No voter expansion is needed.

This establishes \(\mathrm{NP}\)-hardness.

Membership in \(\mathrm{NP}\) and verification time

Relabel the projects as \(P=\{1,\ldots,m\}\). A certificate assigns each project a block label in \(\{1,\ldots,m\}\); projects with the same label form one block. Every partition has such a representation, using \(O(m\log(m+1))\) bits.

Represent blocks by incidence vectors of length \(m\). Each input partition and the certificate partition have at most \(m\) blocks. Comparing every pair of blocks therefore computes all utilities \(u_i(S)\) in \(O(\tau m^3)\) elementary bit comparisons.

The threshold comparison can also be performed exactly in polynomial time. Write \(\mu_i=a_i/b_i\) and \(q=c/d\), with positive denominators, and define
\[ D=d\prod_{i=1}^{\tau}b_i. \]
Then the required comparison is the integer comparison
\[ \sum_{i=1}^{\tau}a_i u_i(S)\frac{D}{b_i} \ge c\frac{D}{d}. \]
The bit length of \(D\) is \(O(L)\), because the total encoded denominator length is at most \(L\). Moreover, \(0\le u_i(S)\le m\) and \(\sum_i\mu_i=1\), so the integer on the left is at most \(mD\). All integers involved have \(O(L+\log(m+1))\) bits, including the right side.

Using schoolbook integer arithmetic, a conservative total verification bound, including representation conversion, is
\[ O\!\left( \tau m^3+ (\tau+1)\bigl(L+m\log(m+1)\bigr)^2 \right). \]
This is polynomial in \(m,\tau,L\), proving membership in \(\mathrm{NP}\).

Conclusion and deterministic upper bound

Combining the reduction and certificate verification proves \(\mathrm{NP}\)-completeness.

For an explicit deterministic upper bound, enumerate all \(m^m\) project-to-block label assignments and verify each. These assignments represent every partition, although some partitions occur repeatedly. The resulting running time is
\[ O\!\left( m^m\left[ \tau m^3+ (\tau+1)\bigl(L+m\log(m+1)\bigr)^2 \right] \right). \]
The hardness transfer and exact rational verification settle the normalized support formulation completely.

⟨structured verdict parsed — rendered above⟩

The output proves the requested problem is \(\mathrm{NP}\)-complete. The cited theorem applies to the exact utility and admissible partitions in the task; the normalization reduction and verification bounds are sound. No major or minor mathematical issues were found.

• The cited hardness result matches the source problem.

The prover states the source decision problem precisely: explicit voter partitions, an integer threshold, and total exact-block-match utility.

I checked the cited paper. Definition 2.3 specifies the decision threshold for total utility; Section 4.1 defines COMP by exact membership of a voter’s block in the output partition; Theorem 4.2 establishes NP-hardness of Total-COMP. The paper’s aggregation domain consists of partitions of the project set, without a restriction to supported blocks. Thus the citation supplies the required hardness result with matching hypotheses. [Jain, Talmon, and Bulteau (2021)](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p665.pdf)

The restriction to source instances with \(n\ge 1\) is legitimate: the cited hardness construction produces a nonempty voter list and a nonempty project set.

• The constructed support instance satisfies every input requirement.

Grouping identical voter partitions produces distinct types \(\Pi_1,\ldots,\Pi_\tau\). Their multiplicities satisfy \(c_i\ge 1\), \(\tau\ge 1\), and \(\sum_i c_i=n\). Consequently, each \(\mu_i=c_i/n\) is a positive binary rational and their sum is exactly one.

The threshold \(q=K/n\) is a permitted rational threshold. The construction preserves the project set and all admissible output partitions. No assumption of equal masses or distinct source voters is introduced.

• The reduction’s equivalence holds for every admissible output.

For each partition \(S\), every voter in group \(i\) has exactly utility \(u_i(S)\). Therefore the displayed grouping identity is correct:
\[ \sum_{i=1}^{\tau}\mu_i u_i(S) = \frac{1}{n}\sum_{j=1}^{n}|\{A\in R_j:A\in S\}|. \]

Since \(n>0\), multiplying the threshold inequality by \(n\) preserves its direction and yields precisely the source inequality. The same \(S\) witnesses both inequalities, establishing both directions of the existential equivalence.

Unsupported output blocks cause no exception: they contribute zero to both objectives, and the identity still holds. Negative or zero thresholds also cause no problem.

• The construction is a polynomial-time many-one reduction.

Canonical project-to-block labels permit equality testing and grouping of explicit partitions in polynomial time. There are at most \(n\) resulting types, each already represented in the source input.

Both numerator and denominator of \(c_i/n\) have \(O(\log(n+1))\) bits. The stated bound for \(K/n\) correctly includes the signed numerator’s magnitude and the denominator. Reducing fractions, if required by the encoding, does not enlarge them and takes polynomial time.

Since the voter list is explicit, \(n\) is bounded by its input length. Thus the output length and construction time are polynomial in the source input length. The hardness claim follows.

• The certificate represents exactly the allowed output partitions.

Assigning each project a label in \(\{1,\ldots,m\}\) defines a partition through its nonempty label classes. Unused labels do not create empty blocks. Conversely, every partition has at most \(m\) blocks and admits such an assignment.

The certificate length \(O(m\log(m+1))\) is correct, including \(m=1\). It is polynomial in the explicit input size. No restriction on supported blocks enters this representation.

• Utility computation and rational comparison are correct.

There are at most \(m\) blocks in each partition. Comparing at most \(m^2\) pairs of length-\(m\) incidence vectors per type gives the claimed \(O(\tau m^3)\) bit-comparison bound. Exact vector equality implements the stated utility.

With positive denominators,
\[ D=d\prod_{i=1}^{\tau}b_i \]
is positive and divisible by each denominator. Hence clearing denominators gives exactly the displayed integer inequality, including when \(q\) is negative.

The denominator bit lengths sum to at most \(L\), so \(D\) has \(O(L)\) bits. The left integer is nonnegative and at most \(mD\), using \(u_i(S)\le m\) and normalized masses. The right integer has \(O(L)\) bits in magnitude because both \(c\) and \(D\) do. These bounds also cover the intermediate products and sums in the indicated computation.

Schoolbook arithmetic therefore supports the conservative verification bound
\[ O\!\left( \tau m^3+ (\tau+1)\bigl(L+m\log(m+1)\bigr)^2 \right). \]
This establishes membership in \(\mathrm{NP}\).

• The conclusion and deterministic upper bound follow.

Combining the valid hardness reduction with membership in \(\mathrm{NP}\) establishes \(\mathrm{NP}\)-completeness. The conditional exclusion of a polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\) is correctly stated.

There are exactly \(m^m\) label assignments, and every partition occurs among them. Repeated representations affect efficiency but not correctness. Multiplying the verification bound by \(m^m\) yields the stated deterministic upper bound, valid also for \(m=1\).

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩