d4-conf-atal-2017-0249 (d4-conf-atal-2017-0249)

Given a candidate set \(A\), bundle size \(k\), threshold \(\ell\), fixed \(\alpha \in \{0,1\}\), and an explicit binary-encoded rational distribution \(\mu\) over a support of \(\tau\) strict rankings of \(A\), does there exist a bundle \(B \subseteq A\), \(|B|=k\), such that \(\left|\{(x,y): x \in B,\ y \notin B,\ p_\mu(x,y)>1/2\}\right|+\alpha\left|\{(x,y): x \in B,\ y \notin B,\ p_\mu(x,y)=1/2\}\right|\ge \ell\), where \(p_\mu(x,y)=\sum_{t:x\succ_t y}\mu_t\)?

Let \(A\) be a candidate set with \(m\geq 1\), let \(1\leq k\leq m\) be an input integer, and let \(\ell\geq 0\) be a binary-encoded integer threshold. Fix \(\alpha\in\{0,1\}\).
A society is given by its support: a list of \(\tau\) distinct strict rankings of \(A\), each with positive binary-rational mass \(\mu_t\), with \(\sum_t\mu_t=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\).
Define \(p_\mu(x,y)=\sum_{t:x\succ_t y}\mu_t\). Pairwise majority ties are permitted and tested exactly.
For a bundle \(B\subseteq A\), define \(s_\alpha(B)=\left|\{(x,y)\in B\times(A\setminus B):p_\mu(x,y)>1/2\}\right|+\alpha\left|\{(x,y)\in B\times(A\setminus B):p_\mu(x,y)=1/2\}\right|\). Bundles remain subsets of candidates of exactly the prescribed size.

For each fixed \(\alpha\in\{0,1\}\), is deciding whether there exists \(B\subseteq A\) with \(|B|=k\) and \(s_\alpha(B)\geq\ell\) solvable in polynomial time, or is it NP-hard?

For a finite, explicitly listed electorate of strict rankings, this decision problem is NP-complete for each fixed \(\alpha\in\{0,1\}\) (Sekar, Sikdar, and Xia, 2017). For the same discrete problem without pairwise majority ties, an optimal bundle is computable in polynomial time.

Result

For each fixed \(\alpha\in\{0,1\}\), the decision problem is \(\mathrm{NP}\)-complete.

The proof uses the discrete hardness theorem given in the question, together with a polynomial reduction that preserves every strict majority and every majority tie. The case without majority ties remains polynomial-time solvable.

1. Exact verification and membership in \(\mathrm{NP}\)

Write each mass as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive binary-encoded integers. Define \(D=\prod_{t=1}^{\tau}b_t\) and \(w_t=a_t(D/b_t)\). Then \(\mu_t=w_t/D\) and \(\sum_t w_t=D\).

The bit length of \(D\) is at most \(1+\sum_t\log_2 b_t\), hence is \(\mathrm{O}(L)\). Because the masses are positive and sum to one, every \(w_t\), and every partial sum of these weights, also has \(\mathrm{O}(L)\) bits.

For distinct candidates \(x,y\), compute \(W(x,y)=\sum_{t:x\succ_t y}w_t\). The majority tests are exactly

• \(p_\mu(x,y)>1/2\) if and only if \(2W(x,y)>D\);
• \(p_\mu(x,y)=1/2\) if and only if \(2W(x,y)=D\).

Thus no approximation is needed. Using elementary integer arithmetic and inverse-position arrays for the rankings, all pairwise majority relations can be computed within the conservative bit-operation bound \(\mathrm{O}((\tau m^2+1)L^2)\). This includes forming the common denominator and integer weights.

A certificate is an \(m\)-bit incidence vector specifying \(B\). Verify that it contains exactly \(k\) candidates, then inspect its \(k(m-k)\) ordered crossing pairs and compute \(s_\alpha(B)\). The score is an integer between zero and \(k(m-k)\), so its comparison with the binary threshold is polynomial-time.

Consequently, certificate verification takes \(\mathrm{O}((\tau m^2+k(m-k)+1)L^2)\) bit operations. The problem belongs to \(\mathrm{NP}\) for both fixed values of \(\alpha\).

2. Polynomial reduction from an explicitly listed electorate

Fix \(\alpha\in\{0,1\}\). We use the supplied theorem that the corresponding decision problem for explicitly listed strict rankings is \(\mathrm{NP}\)-complete; this is Claim 2 of [Sekar, Sikdar, and Xia (2017)](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p33.pdf).

Let a source instance have \(n\geq 1\) explicitly listed rankings, candidate set \(A\), bundle size \(k\), and threshold \(\ell\). We keep \(A,k,\ell\) unchanged.

Ordinarily, grouping equal rankings and assigning each its frequency divided by \(n\) already gives the reduction. The following construction additionally ensures that every output mass is dyadic, so it also covers that narrower interpretation of “binary-rational.”

Let \(N\) be the least power of two satisfying \(N\geq 2n\), and put \(r=(N-2n)/2\). Since \(N\) and \(2n\) are even, \(r\) is a nonnegative integer. Construct an auxiliary electorate by:

• taking two copies of each source ranking;
• choosing any strict ranking \(R\);
• adding \(r\) copies of \(R\) and \(r\) copies of its reverse.

The auxiliary electorate has \(2n+2r=N\) rankings. Group equal rankings into distinct rankings \(R_1,\ldots,R_\tau\), let \(c_t\) be their positive multiplicities, and output masses \(\mu_t=c_t/N\).

These masses are positive dyadic rationals, and their sum is one. The support contains at most \(n+2\) distinct rankings.

Preservation of all majority relations

Fix distinct \(x,y\), and let \(h(x,y)\) be the number of source voters ranking \(x\) above \(y\).

Duplicating the source electorate contributes \(2h(x,y)\) such voters. Since \(R\) and its reverse disagree on every distinct pair, the added rankings contribute exactly \(r\). Therefore

\(p_\mu(x,y)-1/2=(2h(x,y)+r)/N-1/2=(2h(x,y)-n)/N.\)

The source electorate has a strict majority for \(x\) over \(y\) precisely when \(2h(x,y)-n>0\), and a tie precisely when \(2h(x,y)-n=0\). Hence both strict majorities and ties are preserved exactly.

It follows directly from the score definition that, for every \(B\subseteq A\), its source score equals \(s_\alpha(B)\) in the output society. In particular, the source instance has a qualifying bundle of size \(k\) if and only if the output instance does.

Polynomial size and construction time

We have \(N<4n\), so every multiplicity and denominator requires \(\mathrm{O}(\log(n+1))\) bits. The output length is

\(\mathrm{O}(\tau m\log(m+1)+\tau\log(n+1)+\operatorname{bits}(k)+\operatorname{bits}(\ell)),\)

with \(\tau\leq n+2\).

The multiplicities can be computed by sorting the source rankings and incorporating the two added rankings; the auxiliary electorate need not be explicitly expanded. Even explicitly expanding it would produce fewer than \(4n\) rankings. Thus construction takes polynomial time in the explicitly listed source input length.

This is a polynomial many-one reduction for each fixed \(\alpha\). Combined with Section 1, it proves \(\mathrm{NP}\)-completeness.

3. Why the case without majority ties is polynomial

Suppose \(p_\mu(x,y)\neq 1/2\) for every distinct pair. Strict rankings and total mass one imply \(p_\mu(x,y)+p_\mu(y,x)=1\). Thus exactly one candidate strictly defeats the other.

Define \(d^+(x)=|\{y\in A\setminus\{x\}:p_\mu(x,y)>1/2\}|\).

For any bundle \(B\) of size \(k\), summing these degrees counts every victory from \(B\) to its complement, plus every victory between two members of \(B\). Each unordered internal pair contributes exactly once. Therefore

\(s_\alpha(B)=\sum_{x\in B}d^+(x)-\binom{k}{2}.\)

The subtracted term depends only on \(k\). An optimal bundle consequently consists of \(k\) candidates with the largest values of \(d^+(x)\). To justify this selection explicitly, replacing a selected candidate by an unselected candidate of larger degree increases the degree sum; repeated replacements reach such a bundle without decreasing the score.

Compute the majority relations exactly as above, calculate the degrees, and sort them. A conservative running-time bound is \(\mathrm{O}((\tau m^2+m\log(m+1)+1)L^2)\) bit operations, followed by selecting \(k\) candidates and comparing the resulting score with \(\ell\).

Thus rational masses preserve the polynomial algorithm when majority ties are absent. With ties permitted, Section 2 establishes hardness for both specified values of \(\alpha\).

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned problem correctly: for each fixed \(\alpha\in\{0,1\}\), the decision problem is \(\mathrm{NP}\)-complete under the specified support representation. No mathematical gaps or incorrect steps were found.

• Use of the discrete hardness theorem.

The theorem invoked is explicitly supplied by USER_TASK, so it is an admissible premise. The cited [Claim 2 of Sekar, Sikdar, and Xia (2017)](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p33.pdf) states the corresponding fixed-size threshold decision problem is NP-complete for both specified values of \(\alpha\). Its bundle score counts outgoing majority victories and assigns weight \(\alpha\) to ties, matching the source problem used here. The prover preserves the candidate set, prescribed bundle size, and threshold; no hypothesis mismatch occurs.

• Common-denominator arithmetic.

The definitions \(D=\prod_{t=1}^{\tau}b_t\) and \(w_t=a_t(D/b_t)\) are valid because every \(b_t\) divides \(D\). They give \(\mu_t=w_t/D\) and \(\sum_t w_t=D\) exactly.

The claimed bound on the bit length of \(D\) is correct. Positivity and normalization imply \(0<w_t\leq D\), and any sum over a subset of the weights is at most \(D\). Thus all weights and relevant partial sums have \(\mathrm{O}(L)\) bits. Neither reduced fractions nor pairwise coprime denominators are required.

• Exact majority tests and running time.

The equivalences using \(2W(x,y)\) and \(D\) follow directly from the common-denominator representation. Multiplication by two increases the bit length by at most one, so ties are tested exactly within the stated bit bounds.

There are \(\mathrm{O}(m^2)\) candidate pairs and at most \(\tau\) weight contributions per pair. Elementary multiplication and exact division on \(\mathrm{O}(L)\)-bit integers also fit within the conservative bound \(\mathrm{O}((\tau m^2+1)L^2)\). Ranking-position preprocessing does not exceed that bound.

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

An \(m\)-bit incidence vector specifies a candidate subset unambiguously. Checking its cardinality enforces exactly the input size \(k\). There are exactly \(k(m-k)\) crossing pairs, each contributing either zero or one for either fixed value of \(\alpha\). Hence the stated score range is correct.

The threshold comparison remains polynomial even when \(\ell\) exceeds every possible score, since its encoded length is included in \(L\). The verification bound accounts for the relevant input parameters and establishes membership in \(\mathrm{NP}\).

• Validity of the reduction’s output.

For \(n\geq1\), the chosen power of two satisfies \(2n\leq N<4n\). Consequently, \(r=(N-2n)/2\) is a nonnegative integer, and the auxiliary electorate has exactly \(N\) rankings.

Grouping equal rankings produces distinct support entries with positive multiplicities. Their masses \(c_t/N\) sum to one and are dyadic. Only the source rankings and the two additional rankings can appear, so \(\tau\leq n+2\). Possible coincidences between these rankings merely reduce the support size. When \(r=0\), no zero-mass entries need be retained.

• Preservation of strict majorities and ties.

For each distinct pair, duplication contributes \(2h(x,y)\) voters preferring \(x\) to \(y\). A ranking and its reverse contribute exactly one such preference per added pair, giving the additional contribution \(r\).

The displayed calculation is correct: using \(N=2n+2r\), subtracting one half yields numerator \(2h(x,y)-n\) over denominator \(N\). Since \(N>0\), both the sign and vanishing of that numerator agree exactly with the source majority comparison.

Therefore every crossing pair has the same contribution before and after reduction, for both values of \(\alpha\). Score equality holds for every candidate subset, and preserving \(k\) and \(\ell\) proves the required equivalence of decision instances.

• Polynomial construction size and time.

The bounds on multiplicities, denominator length, and support size justify the displayed output-length bound. Sorting explicitly listed rankings and accumulating multiplicities takes polynomial time in the source input length. Even the optional expansion has fewer than \(4n\) entries. The reduction never enumerates all possible rankings or all bundles.

• The case without majority ties and boundary cases.

Strict rankings and total mass one imply \(p_\mu(x,y)+p_\mu(y,x)=1\). Under the stated absence of ties, exactly one direction is a victory. Thus each internal unordered pair contributes exactly once to the sum of selected candidates’ outdegrees, establishing the displayed score identity.

Maximizing that degree sum by selecting \(k\) largest degrees is justified by the exchange argument. Equal degrees cause no difficulty. The stated running-time bound covers exact majority computation, sorting, selection, and threshold comparison.

The arguments also cover \(m=1\) and \(k=m\): the crossing score is zero, and the internal-pair identity remains valid. There is no omitted boundary case affecting either conclusion.

No additional lemma, clarification, or repair is needed. The polynomial result for the restricted case without ties is consistent with NP-completeness when ties are permitted.

⟨structured verdict parsed — rendered above⟩