d4-conf-ijcai-2019-0714 (d4-conf-ijcai-2019-0714)

Given candidates \(C\), committee size \(k\), a finite support of complete rankings \(\pi\) with rational masses \(\mu_\pi\) summing to \(1\), and rational thresholds \(q_1,\ldots,q_\ell\) for \(\ell\le |C|\), decide whether there is a committee \(S\subseteq C\) of size \(k\) such that \(\sum_\pi \mu_\pi\sum_{c\in S}[\operatorname{pos}_\pi(c)\le t]\ge q_t\) for every \(t\in[\ell]\).

Let \(C\) be a candidate set with \(m\ge 1\), and let \(1\le k\le m\) and \(1\le\ell\le m\) be input integers. Each type is a strict complete ranking \(\pi\) of \(C\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_\pi\) a binary rational, with \(\sum_\pi\mu_\pi=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length; state running times in \(m,\tau,L,k,\ell\).
The input also contains nonnegative binary rational thresholds \(q_1,\ldots,q_\ell\). For a committee \(S\subseteq C\), define its mass-weighted \(t\)-Bloc score as \(B_t(S)=\sum_\pi\mu_\pi\sum_{c\in S}\mathbf{1}\{\operatorname{pos}_\pi(c)\le t\}\), where the top position is \(1\). Committees are sets of candidates of cardinality \(k\).

Is deciding whether there exists a committee \(S\) with \(B_t(S)\ge q_t\) for every \(1\le t\le\ell\) solvable in polynomial time, or is it NP-hard?

For an explicitly listed finite electorate with unweighted voters, the corresponding MULTIBLOC decision problem is NP-complete when \(\ell\) is part of the input; for fixed \(\ell\), it is in P ([Kocot et al., 2019](https://www.ijcai.org/proceedings/2019/0055.pdf)). No result for exactly the normalized rational-mass formulation was located in the search.

Result

The normalized rational-mass problem is NP-complete when \(\ell\) is part of the input. Aggregating identical rankings and normalizing voter counts gives a polynomial-time reduction from the explicitly listed, unweighted problem.

Throughout, binary rationals are represented by binary-encoded numerators and positive denominators.

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

A certificate is a list of \(k\) distinct candidates specifying a committee \(S\). Its length is \(O(k\log(m+1))\).

Write each input mass as \(\mu_\pi=a_\pi/b_\pi\), and define
\[ D=\prod_{\pi}b_\pi, \qquad w_\pi=a_\pi(D/b_\pi). \]
Each \(w_\pi\) is a positive integer. The normalization assumption gives
\[ \sum_\pi w_\pi=D. \]
The bit length of \(D\) is \(O(L)\), because it is at most the sum of the bit lengths of the input denominators. Consequently, these integers can be computed in polynomial time without expanding the society into individual voters.

For each supported ranking and each \(t\le\ell\), compute the integer
\[ N_{\pi,t}(S)= \bigl|\{c\in S:\operatorname{pos}_\pi(c)\le t\}\bigr|. \]
Then
\[ B_t(S)=\frac{H_t(S)}{D}, \qquad H_t(S)=\sum_\pi w_\pi N_{\pi,t}(S). \]
Since \(0\le N_{\pi,t}(S)\le k\), we have \(0\le H_t(S)\le kD\). Thus each \(H_t(S)\) has \(O(L+\log(k+1))=O(L)\) bits.

Writing \(q_t=r_t/s_t\), with \(s_t>0\), the required inequality is equivalent to the exact integer comparison
\[ s_tH_t(S)\ge r_tD. \]
All operands have \(O(L)\) bits.

Scanning the rankings, computing prefix counts, and performing these comparisons takes, conservatively,
\[ O\bigl((\tau m+\tau\ell+k+\ell)L^2\bigr) \]
bit operations using schoolbook arithmetic. Checking the certificate’s cardinality and distinctness also fits this bound. This proves membership in \(\mathrm{NP}\).

2. The source hardness theorem

Kocot et al. define \(\ell\)-MULTIBLOC using precisely the rules \(1\)-Bloc through \(\ell\)-Bloc, with separate lower thresholds and a prescribed committee size. Their Theorem 3 states that MULTIBLOC, where \(\ell\) is part of the input, is NP-complete. Their electorate consists of explicitly listed, unweighted voters with strict complete rankings. [Kocot et al., 2019, Section 4](https://www.ijcai.org/proceedings/2019/0055.pdf)

Thus the source problem asks whether some committee \(S\), of size \(k\), satisfies
\[ A_t(S):= \sum_{i=1}^{n}\sum_{c\in S} \mathbf{1}\{\operatorname{pos}_{\pi_i}(c)\le t\} \ge Q_t \quad\text{for every }1\le t\le\ell. \]

We may use nonnegative integer thresholds: these scores are integers, so rational thresholds can be replaced by their ceilings.

We may also restrict to \(n\ge1\) and \(\ell\le m\). Empty-electorate instances are immediately decidable. For \(t\ge m\), every size-\(k\) committee has score \(nk\); hence constraints beyond \(m\) are either automatically satisfied or make the instance immediately infeasible.

3. Reduction by aggregation and normalization

Take such a source instance with \(n\ge1\). Keep its candidate set, committee size \(k\), and parameter \(\ell\).

For every distinct ranking \(\pi\) occurring among the voters, let
\[ a_\pi=\bigl|\{i:\pi_i=\pi\}\bigr|. \]
Output that ranking once, with mass
\[ \mu_\pi=\frac{a_\pi}{n}. \]
Output thresholds
\[ q_t=\frac{Q_t}{n} \quad\text{for }1\le t\le\ell. \]

Every listed mass is positive, and
\[ \sum_\pi\mu_\pi =\frac{\sum_\pi a_\pi}{n} =\frac{n}{n}=1. \]
Therefore the output is a valid normalized society, with support size \(\tau\le n\).

For every size-\(k\) committee \(S\) and every \(t\le\ell\),
\[ \begin{aligned} B_t(S) &=\sum_\pi\frac{a_\pi}{n} \sum_{c\in S}\mathbf{1}\{\operatorname{pos}_\pi(c)\le t\}\\ &=\frac1n \sum_{i=1}^{n}\sum_{c\in S} \mathbf{1}\{\operatorname{pos}_{\pi_i}(c)\le t\}\\ &=\frac{A_t(S)}{n}. \end{aligned} \]
Since \(n>0\), this yields the exact equivalence
\[ B_t(S)\ge q_t \quad\Longleftrightarrow\quad A_t(S)\ge Q_t. \]
It holds simultaneously for every required value of \(t\). Consequently, the source instance is feasible if and only if the output instance is feasible.

Encoding size and construction time

The reduction never enumerates all possible rankings. It only groups the explicitly listed voters.

Each mass \(a_\pi/n\) requires \(O(\log(n+1))\) bits. Each threshold \(Q_t/n\) requires \(O(\operatorname{bits}(Q_t)+\log(n+1))\) bits. The output contains at most \(n\) rankings, all copied from the source.

Grouping can be performed by lexicographically sorting the rankings, using \(O(nm\log(n+1))\) candidate-label comparisons, and then counting repetitions. The rational constructions also take polynomial time in the source bit length. Because the voters are explicitly listed, \(n\) is bounded by that bit length. Hence this is a polynomial-time many-one reduction.

Together with membership in \(\mathrm{NP}\), this proves NP-completeness.

4. Scope of the conclusion

The hardness result concerns variable \(\ell\). For \(\ell=1\), compute each candidate’s first-position mass and choose the \(k\) candidates with largest such masses. Additivity of \(B_1\) proves that this committee maximizes the only constrained score. This gives a polynomial-time algorithm, for example within
\[ O\bigl((\tau m+m\log(m+1))L^2\bigr) \]
bit operations.

The cited fixed-\(\ell\) algorithm for explicitly listed voters does not automatically extend to binary rational masses: clearing denominators can produce an exponentially large integer score range. No extension of that algorithm is needed for the NP-completeness result proved above.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output establishes NP-completeness for the normalized rational-mass problem when \(\ell\) is part of the input. The source theorem matches the required score rules, and the reduction preserves feasibility exactly. I found no major or minor issues requiring repair.

• Target and representation.

The prover addresses the input model in USER_TASK: supported rankings are explicitly listed, masses and thresholds are binary rationals, and committees contain exactly \(k\) distinct candidates. Its numerator–denominator convention makes the rational encoding precise.

The hardness conclusion concerns variable \(\ell\), which is the general decision problem asked about. The output does not claim that the cited fixed-\(\ell\) algorithm extends to rational masses.

• Certificate and membership in \(\mathrm{NP}\).

A list of \(k\) candidate indices has the stated length \(O(k\log(m+1))\). Membership in the candidate set, cardinality, and distinctness are polynomial-time checks.

The common denominator
\[ D=\prod_{\pi}b_\pi \]
is positive, and each quotient \(D/b_\pi\) is an integer. Positive supported masses therefore give positive integers \(w_\pi=a_\pi(D/b_\pi)\). Multiplying the normalization equation by \(D\) verifies
\[ \sum_\pi w_\pi=D. \]

The bit length of a product is bounded by the sum of the factors’ bit lengths. Hence \(D\) has \(O(L)\) bits, even when its numerical value is exponentially large. The construction does not require enumerating \(D\) voters.

Each prefix count satisfies \(0\le N_{\pi,t}(S)\le k\). Consequently,
\[ 0\le H_t(S)=\sum_\pi w_\pi N_{\pi,t}(S)\le kD. \]
The stated bit bound follows. In particular, \(\log(k+1)=O(L)\), since \(k\) is part of the input.

For a threshold with positive denominator \(s_t\), multiplication by \(Ds_t>0\) gives precisely
\[ B_t(S)\ge q_t \quad\Longleftrightarrow\quad s_tH_t(S)\ge r_tD. \]
There is no rounding or numerical approximation. The comparison operands have \(O(L)\) bits.

The verification bound
\[ O\bigl((\tau m+\tau\ell+k+\ell)L^2\bigr) \]
is a valid conservative bound using schoolbook arithmetic. It accommodates denominator products, exact divisions, prefix counts, weighted sums, certificate checks, and threshold comparisons.

• Applicability of the cited hardness theorem.

I checked the cited paper. Its election model uses voters ranking all candidates; its committee scores sum candidate scores over voters. It defines \(t\)-Bloc using the indicator for positions at most \(t\), defines \(\ell\)-MULTIBLOC using all rules from \(1\)-Bloc through \(\ell\)-Bloc, and states NP-completeness for MULTIBLOC when \(\ell\) is input. Thus the cited theorem has the required committee size, score functions, and separate lower-bound constraints. [Kocot et al., Sections 2–4](https://www.ijcai.org/proceedings/2019/0055.pdf)

Replacing rational source thresholds by their ceilings preserves the constraints because source scores are integers. Nonnegativity is preserved.

The source restrictions are also justified. Empty electorates are immediately decidable. For \(t\ge m\), every candidate qualifies, so every size-\(k\) committee has score \(nk\). Constraints beyond \(m\) can therefore be removed or identified as infeasible. These polynomial-time exceptional-case checks do not undermine the use of the hardness theorem.

• Validity of the reduction’s output.

Every multiplicity \(a_\pi\) is positive, and the multiplicities sum to \(n\). Since \(n\ge1\), all output masses are positive and their sum is exactly one.

Aggregation produces one entry per distinct supported ranking, so \(\tau\le n\). The candidate set, \(k\), and the retained \(\ell\) remain within the target’s required domains. Nonnegative source thresholds give valid nonnegative rational output thresholds.

• Correctness of the feasibility equivalence.

Grouping voters with identical rankings preserves their total contribution for every committee and every cutoff. Thus the displayed computation correctly establishes
\[ B_t(S)=\frac{A_t(S)}{n}. \]
The output threshold is \(q_t=Q_t/n\). Because \(n>0\), the resulting equivalence preserves the inequality direction.

This identity holds for every size-\(k\) committee and every required \(t\). Therefore it proves both directions of the simultaneous feasibility equivalence, rather than merely preserving an aggregate score.

• Reduction size and running time.

The stated mass and threshold encoding bounds are correct. All output rankings come from the explicitly listed source electorate, and there are at most \(n\) of them.

The sorting bound counts candidate-label comparisons, as explicitly stated. Accounting for their bit cost still gives polynomial time in the source input length. Computing multiplicities and constructing the rational numbers also take polynomial time. No step expands a compactly represented electorate or enumerates possible rankings.

• Additional scope statements.

For \(\ell=1\), additivity makes selection of the \(k\) largest first-position masses optimal. Ties cause no problem, and the stated running-time bound is conservative. Decision additionally requires comparing the selected committee’s score with \(q_1\), which fits that bound.

The observation about denominator clearing is appropriately limited: the resulting integer score range can be exponentially large. It explains why the cited unweighted algorithm does not automatically provide a polynomial-time rational-mass algorithm; it asserts no unsupported fixed-\(\ell\) hardness result.

Repair feedback: None required. The general complexity conclusion is established; the output appropriately leaves the rational-mass fixed-\(\ell\) cases beyond \(\ell=1\) unclassified.

⟨structured verdict parsed — rendered above⟩