d4-conf-aaai-2018-0671 (d4-conf-aaai-2018-0671)

Given \(C\), \(k\), a committee \(W\subseteq C\) of size \(k\), and approval types \(A_t\subseteq C\) with positive rational masses \(\mu_t\) summing to \(1\), decide whether every \(1\le\ell\le k\) and every submass vector \(0\le\nu_t\le\mu_t\) with \(\sum_t\nu_t\ge\ell/k\) satisfies \(\left|W\cap\bigcup_{t\in Q}A_t\right|\ge\ell\) whenever \(Q=\{t:\nu_t>0\}\) has \(\left|\bigcap_{t\in Q}A_t\right|\ge\ell\).

Let \(C\) be a finite candidate set with \(m=|C|\), let \(k\) be an integer with \(1\le k\le m\), and let \(W\subseteq C\) satisfy \(|W|=k\).
A society is given by its support: a list of \(\tau\) distinct approval types \(A_t\subseteq C\), possibly empty, with positive binary rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible approval sets. Let \(L\) be the total input bit length; state running times in \(m,\tau,L,k\).
A submass vector has real coordinates \(0\le\nu_t\le\mu_t\), and its participating types are \(Q=\{t:\nu_t>0\}\). The committee satisfies mass-PJR if, for every integer \(1\le\ell\le k\) and every submass vector with \(\sum_t\nu_t\ge\ell/k\), the implication \(\left|\bigcap_{t\in Q}A_t\right|\ge\ell\Rightarrow\left|W\cap\bigcup_{t\in Q}A_t\right|\ge\ell\) holds.

Is detecting a violation of mass-PJR \(\mathrm{NP}\)-hard or in \(\mathrm{P}\), equivalently, is checking mass-PJR \(\mathrm{coNP}\)-hard or in \(\mathrm{P}\)?

For finite unweighted electorates, checking PJR is \(\mathrm{coNP}\)-complete; it is also FPT in the number of voters or candidates. [Verified discrete results](https://ojs.aaai.org/index.php/AAAI/article/download/11478/11337).
No result settling this exact submass formulation was located in the literature search.

Mass-PJR violation detection is \(\mathrm{NP}\)-complete

Checking mass-PJR is \(\mathrm{coNP}\)-complete. The key is that any violating submass vector can be replaced by the full masses of its participating types. This permits an exact reduction from discrete PJR.

Here, rational masses are represented by numerators and denominators encoded in binary.

1. Eliminating the submass quantifier

For a nonempty set of types \(Q\subseteq\{1,\ldots,\tau\}\), define
\(\mu(Q)=\sum_{t\in Q}\mu_t\),
\(I(Q)=\bigcap_{t\in Q}A_t\), and
\(U(Q)=\bigcup_{t\in Q}A_t\).

Lemma. A committee violates mass-PJR if and only if there exist a nonempty \(Q\) and an integer \(1\le\ell\le k\) such that
\(\mu(Q)\ge\ell/k\),
\(|I(Q)|\ge\ell\), and
\(|W\cap U(Q)|<\ell\).

Proof. Suppose a submass vector \(\nu\) witnesses a violation, and let \(Q=\{t:\nu_t>0\}\). Its positive total mass makes \(Q\) nonempty. Because \(\nu_t\le\mu_t\),
\(\mu(Q)\ge\sum_t\nu_t\ge\ell/k\).
The intersection and union conditions are precisely those in the lemma.

Conversely, given such \(Q,\ell\), set \(\nu_t=\mu_t\) for \(t\in Q\) and \(\nu_t=0\) otherwise. Since every listed mass is positive, the participating types are exactly \(Q\), and all three violation conditions hold. \(\square\)

Thus arbitrary real coordinates create no additional difficulty for certificates.

2. Membership in \(\mathrm{NP}\)

A certificate consists of \(Q\), encoded by \(\tau\) bits, and \(\ell\), encoded using \(O(\log(k+1))\) bits. The verifier checks the three conditions in the lemma.

Here is an explicit polynomial bound for exact arithmetic. Write \(\mu_t=a_t/b_t\), and let \(D=\prod_{t=1}^{\tau}b_t\). Since \(L\) includes all denominator encodings, \(D\) has \(O(L)\) bits. Put
\(s_t=a_t(D/b_t)\).
Then the mass inequality is equivalent to the integer comparison
\(k\sum_{t\in Q}s_t\ge\ell D\).

Computing these integers with schoolbook arithmetic takes \(O(\tau L^2)\) bit operations. Their bit lengths are \(O(L)\): each mass is at most one, and their total is one. Using characteristic vectors for approval sets, the intersection and union checks take \(O(\tau m)\) operations. Including input reading, a conservative verification bound is
\(O(L+\tau m+\tau L^2)\).

Therefore violation detection belongs to \(\mathrm{NP}\), and mass-PJR checking belongs to \(\mathrm{coNP}\).

3. Polynomial reduction from discrete PJR

We use the established theorem that checking PJR for an explicitly listed, finite unweighted electorate and a specified size-\(k\) committee is \(\mathrm{coNP}\)-complete. Its definition uses exactly the conditions
\(|V|\ge\ell n/k\),
\(\left|\bigcap_{i\in V}B_i\right|\ge\ell\), and
\(\left|W\cap\bigcup_{i\in V}B_i\right|<\ell\)
for a violating voter group \(V\). Consequently, detecting a discrete PJR violation is \(\mathrm{NP}\)-complete. See [Aziz et al., Theorem 3](https://ojs.aaai.org/index.php/AAAI/article/download/11478/11337).

Take such an instance with voters \(\{1,\ldots,n\}\), ballots \(B_i\subseteq C\), and committee \(W\). Partition the voters according to identical ballots. Let the distinct ballots be \(A_1,\ldots,A_\tau\), and let
\(n_t=|\{i:B_i=A_t\}|\).

Construct the mass instance by retaining \(C,k,W\) and assigning
\(\mu_t=n_t/n\).

This satisfies every required input condition: the types are distinct, their masses are positive binary-encoded rationals, and
\(\sum_t\mu_t=1\).
Moreover, \(m,k\) are unchanged, \(\tau\le n\), and the output length is
\(O(\tau m+\tau\log(n+1)+m)\).
Grouping explicitly listed ballots and counting their multiplicities takes polynomial time in the source input length. No enumeration of all possible approval sets is needed.

We prove preservation of violations in both directions.

Discrete violation implies mass violation

Suppose \(V\) witnesses a discrete violation at level \(\ell\). Let
\(Q=\{t:\text{some voter in }V\text{ has ballot }A_t\}\).

Every voter in \(V\) belongs to a type in \(Q\), so
\(\mu(Q)=\sum_{t\in Q}n_t/n\ge |V|/n\ge\ell/k\).

Every type in \(Q\) occurs in \(V\), and every ballot occurring in \(V\) is a type in \(Q\). Repetition of an identical set changes neither intersection nor union. Hence
\(I(Q)=\bigcap_{i\in V}B_i\) and
\(U(Q)=\bigcup_{i\in V}B_i\).

The lemma therefore gives a mass-PJR violation.

Mass violation implies discrete violation

Suppose the constructed mass instance violates mass-PJR. By the lemma, take witnessing \(Q,\ell\). Let \(V_Q\) contain all voters whose types lie in \(Q\).

Then
\(|V_Q|=n\mu(Q)\ge\ell n/k\).

Each type has positive multiplicity, so every type in \(Q\) occurs in \(V_Q\). Again,
\(\bigcap_{i\in V_Q}B_i=I(Q)\) and
\(\bigcup_{i\in V_Q}B_i=U(Q)\).

Thus \(V_Q\) witnesses a discrete PJR violation.

This proves a polynomial many-one reduction from discrete violation detection to mass-PJR violation detection, establishing \(\mathrm{NP}\)-hardness.

4. Conclusion and an explicit search bound

Combining hardness with certificate verification, mass-PJR violation detection is \(\mathrm{NP}\)-complete, and mass-PJR checking is \(\mathrm{coNP}\)-complete.

For completeness, an exact algorithm enumerates the nonempty subsets \(Q\) of the listed support. Set
\(r=|W\cap U(Q)|\) and \(h=|I(Q)|\).
A violation exists for this \(Q\) precisely when
\(r<k\),
\(h\ge r+1\), and
\(k\mu(Q)\ge r+1\).

Indeed, any witnessing integer satisfies \(\ell\ge r+1\), so these conditions are necessary; conversely, they make \(\ell=r+1\) a witness. This avoids a separate loop over levels.

With the arithmetic bounds above, the algorithm runs in
\(O(L+2^\tau(\tau m+\tau L^2))\).
In particular, it is fixed-parameter tractable in the actual support size \(\tau\).

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves the stated submass formulation: violation detection is \(\mathrm{NP}\)-complete, and checking mass-PJR is \(\mathrm{coNP}\)-complete. No substantive or expositional gaps require repair.

1. Eliminating the submass quantifier

Both directions of the lemma are valid.

For a violating submass vector, \(\ell\ge 1\) and \(k\ge 1\) imply
\(\sum_t\nu_t\ge\ell/k>0\), so its participating set \(Q\) is nonempty. Summing the coordinate inequalities gives
\(\mu(Q)\ge\sum_t\nu_t\ge\ell/k\).
The intersection and union depend only on participating types, so the other two witness conditions are preserved exactly.

Conversely, setting each participating coordinate to its full mass is admissible. Positivity of every \(\mu_t\) ensures that the participating set remains exactly \(Q\). Thus the constructed vector witnesses the required violation.

This argument correctly handles arbitrary real submasses without requiring a finite encoding of those real coordinates.

2. Certificate verification and arithmetic

The certificate has polynomial length: \(\tau\) membership bits and \(O(\log(k+1))\) bits for \(\ell\). The verifier must check \(1\le\ell\le k\), nonemptiness, and the three lemma conditions; these are precisely the stated requirements.

The arithmetic construction is correct:

• The product \(D=\prod_t b_t\) has bit length bounded by the sum of denominator bit lengths, hence \(O(L)\).
• Each \(D/b_t\) is an integer, and \(s_t=a_t(D/b_t)=D\mu_t\).
• Since the masses sum to one, \(\sum_t s_t=D\), so every subset sum is at most \(D\).
• Multiplication by \(k\) or \(\ell\) preserves an \(O(L)\) bit bound because their encodings are included in \(L\).
• Multiplying by the positive quantity \(kD\) gives exactly the stated integer comparison.

Computing the product, exact quotients, scaled numerators, subset sum, and final comparison fits the conservative schoolbook bound \(O(\tau L^2)\). The set computations fit \(O(\tau m)\) using characteristic vectors. Thus the stated verification bound
\(O(L+\tau m+\tau L^2)\) is valid.

The conclusions of membership in \(\mathrm{NP}\) and \(\mathrm{coNP}\) follow.

3. Cited discrete theorem

The citation is accurate. Theorem 3 states coNP-completeness for checking PJR given an election, target committee size \(k\), and committee \(W\) of size \(k\). The paper’s definition uses the same group-size threshold, common-approval requirement, union-based representation condition, and integer levels as the prover states. [Aziz et al., definitions and Theorem 3](https://ojs.aaai.org/index.php/AAAI/article/download/11478/11337).

Taking complements therefore establishes the asserted NP-completeness of discrete violation detection. The cited result applies to the source instances used by the reduction.

4. Reduction construction and encoding

Grouping equal ballots produces distinct approval types with positive multiplicities. For the positive-size electorates used here, assigning \(\mu_t=n_t/n\) gives positive rational masses summing to one.

Each numerator and denominator needs \(O(\log(n+1))\) bits. The stated output-size bound is valid with characteristic-vector approval encoding. Grouping and counting explicitly listed ballots takes polynomial time in the source input length.

The construction preserves \(C\), \(k\), and \(W\), including \(1\le k\le m\) and \(|W|=k\). Empty ballots are permitted by the target formulation and cause no construction problem.

5. Preservation of violations

Discrete to mass. The chosen \(Q\) contains exactly the ballot types occurring in \(V\). Taking their full multiplicities can only increase the relevant mass. Repeating identical ballots changes neither their intersection nor their union. Consequently, all three lemma conditions hold at the original level \(\ell\).

Mass to discrete. Taking every voter of each witnessing type gives
\(|V_Q|=n\mu(Q)\ge\ell n/k\). Positive multiplicities ensure that every selected type actually occurs. The intersection and union therefore agree exactly with \(I(Q)\) and \(U(Q)\), preserving both remaining conditions.

These directions prove the required many-one equivalence. The reduction establishes NP-hardness for the exact target formulation.

6. Search criterion, runtime, and edge cases

For fixed nonempty \(Q\), an integer witness must satisfy \(\ell\ge r+1\). Hence the three stated conditions are necessary. Conversely, those conditions make \(\ell=r+1\) a valid level with \(1\le\ell\le k\), sufficient common approval, sufficient mass, and insufficient committee representation.

Enumerating fewer than \(2^\tau\) subsets with the stated per-subset computations gives the claimed runtime. Its dependence on \(k\) is covered by the input bit length and \(k\le m\). The FPT conclusion in actual support size \(\tau\) is justified.

Empty participating sets cannot witness a violation. A selected empty approval type forces the intersection size to zero. Equality at the mass threshold is accepted correctly. The level endpoints and cases \(k=1\) and \(k=m\) are covered by the same arguments.

No repair feedback is needed.

⟨structured verdict parsed — rendered above⟩