d4-conf-ijcai-2011-0342 (d4-conf-ijcai-2011-0342)

Given a candidate set \(A\), a support \(T\) of complete rankings over \(A\) with positive rational masses \(\mu_t\) summing to \(1\), an integer \(K\le |A|\), and a rational threshold \(q\ge 0\), does there exist a slate \(\Phi\subseteq A\) with \(|\Phi|=K\) such that \(\sum_{t\in T}\mu_t\max_{a\in\Phi}(|A|-\operatorname{pos}_t(a))\ge q\)?

Given a candidate set \(A\) with \(m=|A|\ge 1\), a society is specified by its support \(T\): a list of \(\tau\) distinct strict complete rankings over \(A\), each with positive binary-rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible rankings.
Let \(\operatorname{pos}_t(a)\in\{1,\ldots,m\}\) denote the position of \(a\) in ranking \(t\), with position \(1\) best. The remaining inputs are an integer \(1\le K\le m\) and a binary-rational threshold \(q\ge 0\). Let \(L\) be the total input bit length.
A slate is a subset \(\Phi\subseteq A\) with \(|\Phi|=K\); candidate selection is indivisible. Its welfare is \(W(\Phi)=\sum_{t\in T}\mu_t\max_{a\in\Phi}(m-\operatorname{pos}_t(a))\).

Is deciding whether some slate \(\Phi\) satisfies \(W(\Phi)\ge q\) solvable in polynomial time in \(m,\tau,K,L\), or is it NP-hard?

For an explicitly listed finite electorate, deciding whether a slate of exactly \(K\) candidates attains a given nonnegative threshold of total Borda welfare is NP-complete.

Conclusion

The decision problem is \(\mathrm{NP}\)-complete. This holds even when every mass and the threshold are dyadic rationals, meaning rationals whose denominators are powers of two.

The proof uses the explicitly listed electorate hardness result supplied in the question.

Membership in \(\mathrm{NP}\)

A certificate is a slate \(\Phi\subseteq A\) containing exactly \(K\) distinct candidates.

For each listed ranking \(t\), compute the integer
\(b_t(\Phi)=\max_{a\in\Phi}(m-\operatorname{pos}_t(a))\).
Then evaluate \(W(\Phi)=\sum_{t\in T}\mu_t b_t(\Phi)\) and compare it with \(q\).

These computations take polynomial time. In particular, exact rational arithmetic suffices: a common denominator obtained by multiplying the input denominators has bit length at most the sum of their bit lengths. Since \(0\le b_t(\Phi)\le m-1\), the resulting numerators also have polynomial bit length. Thus the problem belongs to \(\mathrm{NP}\).

A polynomial reduction establishing hardness

Consider an instance of the supplied \(\mathrm{NP}\)-complete problem with an explicitly listed electorate of \(n\ge1\) voters, rankings \(t_1,\ldots,t_n\), candidate set \(A\), slate size \(K\), and nonnegative threshold \(B\). Its total welfare is
\(S(\Phi)=\sum_{i=1}^{n}b_{t_i}(\Phi)\).

Because \(S(\Phi)\) is an integer, replace \(B\) by the integer \(Q=\lceil B\rceil\). This preserves the answer and takes polynomial time.

Simply aggregating equal rankings and assigning their relative frequencies would preserve normalized welfare exactly. To ensure that the output satisfies even the stricter dyadic interpretation of “binary-rational,” we use the following padding construction.

Choose \(N\) to be the least power of two satisfying
\(N\ge n\bigl(n(m-1)+1\bigr)\).
Write \(N=Dn+r\), where \(D=\lfloor N/n\rfloor\) and \(0\le r<n\). Then
\(D\ge n(m-1)+1>r(m-1)\).

Let \(T\) be the set of distinct rankings appearing in the source electorate, and let \(c_t\) be the multiplicity of ranking \(t\). Fix one ranking \(t_0\in T\). Assign the masses
\(\mu_{t_0}=(Dc_{t_0}+r)/N\) and
\(\mu_t=Dc_t/N\) for \(t\ne t_0\).
Set the output threshold to \(q=DQ/N\), retaining \(A\) and \(K\).

Every mass is positive, and
\(\sum_{t\in T}\mu_t=(D\sum_{t\in T}c_t+r)/N=(Dn+r)/N=1\).
All masses and \(q\) are dyadic rationals. The support contains only distinct strict complete rankings, as required.

Preservation of the answer

For every slate \(\Phi\) of size \(K\), the constructed welfare satisfies
\(NW(\Phi)=DS(\Phi)+r\,b_{t_0}(\Phi)\).

If the source instance is a yes-instance, choose \(\Phi\) with \(S(\Phi)\ge Q\). Since \(b_{t_0}(\Phi)\ge0\), we obtain
\(NW(\Phi)\ge DQ=Nq\).
Thus the constructed instance is a yes-instance.

Conversely, if the source instance is a no-instance, every size-\(K\) slate satisfies \(S(\Phi)\le Q-1\). Using \(b_{t_0}(\Phi)\le m-1\), we obtain
\(NW(\Phi)\le D(Q-1)+r(m-1)<DQ=Nq\),
where the strict inequality follows from \(r(m-1)<D\). Thus the constructed instance is a no-instance.

Polynomial encoding size

The chosen power of two satisfies
\(N<2n\bigl(n(m-1)+1\bigr)\),
so its bit length is \(O(\log n+\log m)\). There are at most \(n\) support rankings, each already present in the explicitly listed input. Their multiplicities, the output masses, and the threshold can all be computed and encoded in polynomial time.

No replicated electorate needs to be explicitly constructed: the factors \(D\) and the padding \(r\) are incorporated directly into the masses.

Consequence

The reduction proves \(\mathrm{NP}\)-hardness, and the certificate argument proves membership in \(\mathrm{NP}\). Hence polynomial-time solvability in \(m,\tau,K,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned problem. The argument is correct and rigorous: it establishes $\mathrm{NP}$-completeness even with dyadic masses and threshold. No substantive or expositional gaps require repair.

• Membership in $\mathrm{NP}$. A certificate lists exactly $K$ distinct candidates. Its validity can be checked against $A$, and each ranking’s maximum Borda score can be computed in polynomial time. The exact arithmetic argument is sound: multiplying the input denominators produces a denominator whose bit length is at most their combined bit length. Multiplying by scores bounded by $m-1$ and summing $\tau$ terms preserves polynomial bit length. Comparing with the rational threshold is therefore polynomial-time.

• Use of the supplied hardness result. The source problem is precisely the explicitly listed electorate problem supplied in USER_TASK, with indivisible candidate selection, exactly $K$ candidates, and total Borda welfare. The prover uses that result as an assumption supplied by the task; no additional hardness theorem needs verification. Restricting to nonempty electorates is harmless: empty-electorate instances have zero welfare for every valid slate and are immediately decidable.

• Threshold rounding. Every source welfare $S(\Phi)$ is an integer, so $S(\Phi)\ge B$ is equivalent to $S(\Phi)\ge Q$, where $Q=\lceil B\rceil$. Computing this ceiling from a binary-encoded rational threshold takes polynomial time. Nonnegativity of $B$ implies $Q\ge0$, ensuring the output threshold is allowed.

• Padding parameters and valid output. Put $H=n(n(m-1)+1)$. Since $H\ge1$, the least power of two $N\ge H$ exists and satisfies $H\le N<2H$. Consequently,

$$ D=\lfloor N/n\rfloor\ge n(m-1)+1. $$
Because $0\le r<n$ and $m-1\ge0$, this yields $D>r(m-1)$, including when $m=1$. Every multiplicity $c_t$ is positive and $D\ge1$, so every constructed mass is positive. Their sum is exactly $(Dn+r)/N=1$. Aggregation produces distinct rankings, and denominators dividing the power of two $N$ make all masses and the threshold dyadic.

• Preservation of the answer. The identity

$$ NW(\Phi)=DS(\Phi)+r\,b_{t_0}(\Phi) $$
follows directly from the assigned masses. For a source yes-instance, nonnegativity of the padding contribution gives $NW(\Phi)\ge DQ$. For a source no-instance, integrality gives $S(\Phi)\le Q-1$ for every size-$K$ slate, and therefore
$$ NW(\Phi)\le D(Q-1)+r(m-1)<DQ. $$
The strict inequality is justified by the verified bound $r(m-1)<D$. Both implications use the same unchanged candidate set and slate size.

• Polynomial construction and edge cases. The bound on $N$ gives polynomial bit lengths for $N,D,r$ and all mass numerators. The threshold numerator $DQ$ also has polynomial bit length, including when the source threshold is large. Grouping explicitly listed rankings and computing their multiplicities takes polynomial time, and at most $n$ rankings are output. No electorate expansion is required. The argument also covers $r=0$, $m=1$, $K=m$, and $Q=0$; none invalidates the construction or equivalence.

The resulting polynomial reduction establishes $\mathrm{NP}$-hardness for the required support representation, and the certificate argument establishes membership in $\mathrm{NP}$. No additional clarification is needed.

⟨structured verdict parsed — rendered above⟩