Discovering Consistent Subelections (aamas24-00109)

Given a finite candidate set \(C\), ranking types \(T=\mathcal{L}(C)\), a rational distribution \(\mu\) over \(T\), an integer \(q\), and rational \(\alpha\), decide whether there exist \(C'\subseteq C\) with \(|C'|\ge q\) and an order \(\pi\) on \(C'\) such that \(\sum_{t\in T:\,t|_{C'}=\pi}\mu_t\ge\alpha\); equivalently, maximize the mass of types agreeing on the selected candidate order.

Definitions. Let \(C\) be a finite candidate set and let \(S_C\) be its complete rankings. The input explicitly lists a rational probability distribution \(\mu\) by its nonzero masses \(\mu_\sigma\), together with \(k\in\mathbb{N}\) and \(\beta\in\mathbb{Q}\). For \(C'\subseteq C\) and an order \(\pi\) of \(C'\), its supporting mass is \(\sum_{\sigma:\sigma|_{C'}=\pi}\mu_\sigma\). Decide whether some \(C'\) with \(|C'|\ge k\) and some \(\pi\) have supporting mass at least \(\beta\).

Target. Is this distributional hidden-identity problem solvable in polynomial time, or is it NP-hard?

Nearest known results. The finite-profile analogue, in which one seeks at least \(m'\) candidates and at least \(n'\) voters inducing one common order, is NP-complete. No result for the exact distributional formulation above was verified.

Complexity of Distributional Hidden Identity

Theorem

The distributional hidden-identity decision problem is \(\mathrm{NP}\)-complete. In particular, it is \(\mathrm{NP}\)-hard even when the input distribution is an empirical distribution obtained by normalizing a finite voter profile.

Source problem

Use the stated \(\mathrm{NP}\)-complete finite-profile problem:

• The input consists of a candidate set \(C\), voters \(V=\{1,\ldots,n\}\), a complete ranking \(\sigma_i\in S_C\) for every \(i\in V\), and integers \(m'\) and \(n'\).
• The question is whether there exist \(C'\subseteq C\) with \(|C'|\geq m'\), an order \(\pi\) of \(C'\), and at least \(n'\) voters whose rankings restricted to \(C'\) all equal \(\pi\).

We assume \(n\geq 1\), as is standard for a voter profile.

Reduction

For every ranking \(\sigma\in S_C\), let

\[ a_\sigma=\bigl|\{i\in V:\sigma_i=\sigma\}\bigr|. \]

Construct the explicitly supported distribution \(\mu\) by listing precisely those rankings for which \(a_\sigma>0\), with mass

\[ \mu_\sigma=\frac{a_\sigma}{n}. \]

Set

\[ k=m' \qquad\text{and}\qquad \beta=\frac{n'}{n}. \]

This is a probability distribution because every mass is positive and

\[ \sum_{\sigma:a_\sigma>0}\mu_\sigma = \frac{1}{n}\sum_{\sigma:a_\sigma>0}a_\sigma = \frac{n}{n} = 1. \]

Polynomial-time encoding

There are at most \(n\) distinct rankings with positive mass. Duplicate voter rankings can be aggregated by sorting or hashing their explicit ranking encodings.

Each numerator \(a_\sigma\), the common denominator \(n\), and the numerator \(n'\) require \(O(\log n)\) bits. Thus the constructed distribution and threshold have size polynomial in the finite-profile input size, and the reduction is computable in polynomial time.

Correctness of the reduction

Fix any \(C'\subseteq C\) and any order \(\pi\) of \(C'\). Let

\[ N(C',\pi) = \bigl|\{i\in V:\sigma_i|_{C'}=\pi\}\bigr|. \]

The supporting mass of \(\pi\) under the constructed distribution is

\[ \begin{aligned} \sum_{\sigma:\sigma|_{C'}=\pi}\mu_\sigma &= \sum_{\sigma:\sigma|_{C'}=\pi}\frac{a_\sigma}{n} \\ &= \frac{1}{n} \sum_{\sigma:\sigma|_{C'}=\pi}a_\sigma \\ &= \frac{N(C',\pi)}{n}. \end{aligned} \]

Consequently,

\[ \sum_{\sigma:\sigma|_{C'}=\pi}\mu_\sigma\geq\beta \]

holds if and only if

\[ \frac{N(C',\pi)}{n}\geq\frac{n'}{n}, \]

which, since \(n>0\), holds if and only if

\[ N(C',\pi)\geq n'. \]

Therefore:

• If the finite-profile instance is a yes-instance, its candidate set \(C'\) and common order \(\pi\) have supporting mass at least \(\beta\).
• If the distributional instance is a yes-instance, at least \(n'\) original voters induce its witnessing order \(\pi\) on its witnessing set \(C'\).

The two instances are therefore equivalent. Since the finite-profile problem is \(\mathrm{NP}\)-hard, the distributional problem is \(\mathrm{NP}\)-hard.

Membership in \(\mathrm{NP}\)

A certificate consists of:

• a subset \(C'\subseteq C\), and
• a permutation \(\pi\) of \(C'\).

The verifier first checks \(|C'|\geq k\). For every explicitly listed support ranking \(\sigma\), it computes \(\sigma|_{C'}\), tests whether this restriction equals \(\pi\), and sums the corresponding rational masses.

Restriction and comparison take polynomial time. Exact addition and comparison of binary-encoded rationals also take polynomial time: throughout the computation, numerator and denominator bit lengths are bounded by the sum of the input bit lengths. The verifier can therefore decide whether the supporting mass is at least \(\beta\) in polynomial time.

Hence the problem belongs to \(\mathrm{NP}\).

Conclusion

The explicit rational distribution does not relax or fractionalize the finite-profile problem. Normalizing voter multiplicities by \(n\) preserves every supporting-count inequality exactly. The distributional hidden-identity problem is therefore \(\mathrm{NP}\)-complete.

⟨structured verdict parsed — rendered above⟩

Verification Report

Summary

The prover correctly establishes that the distributional hidden-identity problem is \(\mathrm{NP}\)-complete, assuming the stated finite-profile analogue is available as an \(\mathrm{NP}\)-complete source problem. The reduction is polynomial, preserves yes-instances in both directions, and produces a valid explicitly represented rational distribution. The membership-in-\(\mathrm{NP}\) argument is also sound.

Step-by-step audit

• Choice of source problem. The prover uses exactly the finite-profile problem identified in the task as \(\mathrm{NP}\)-complete. Its witnesses consist of a candidate subset, a common restricted order, and at least \(n'\) supporting voters. This matches the structure needed by the reduction.

• Construction of the distribution. For each distinct ranking \(\sigma\), the multiplicity \(a_\sigma\) is normalized to \(\mu_\sigma=a_\sigma/n\). Since the multiplicities sum to \(n\), the resulting masses are positive on the listed support and sum to \(1\). Thus the construction produces a valid probability distribution.

• Parameter mapping. Setting \(k=m'\) preserves the candidate-set size condition. Setting \(\beta=n'/n\) translates the required number of supporting voters into the corresponding empirical probability mass.

• Polynomial encoding. There are at most \(n\) distinct rankings in the support. Each multiplicity and denominator has \(O(\log n)\) bits, while each ranking already has a polynomial-size explicit representation. Aggregating duplicates and producing the rational masses can therefore be done in polynomial time.

• Preservation of supporting mass. For every fixed \(C'\) and \(\pi\), the calculation

\[ \sum_{\sigma:\sigma|_{C'}=\pi}\mu_\sigma = \frac{N(C',\pi)}{n} \]
is correct: grouping voters by their full ranking neither loses nor duplicates any voter whose restriction equals \(\pi\).

• Equivalence of thresholds. Because \(n>0\), the inequality \(N(C',\pi)/n\geq n'/n\) is equivalent to \(N(C',\pi)\geq n'\). Hence the reduction preserves both yes- and no-instances.

• Hardness conclusion. The established polynomial-time many-one reduction from the stated \(\mathrm{NP}\)-complete finite-profile problem proves \(\mathrm{NP}\)-hardness. It also proves the stronger claim that hardness persists for empirical distributions.

• Membership in \(\mathrm{NP}\). A subset \(C'\) and an order \(\pi\) form a polynomial-size certificate. Restricting every explicitly listed ranking, comparing it with \(\pi\), summing the selected rational masses exactly, and comparing the result with \(\beta\) are polynomial-time operations. The stated bit-length bound for rational arithmetic is sufficient.

• Edge conditions. The construction explicitly assumes \(n\geq1\), which is necessary for normalization and is standard for the cited voter-profile problem. Values such as \(n'>n\), \(m'>|C|\), \(\beta>1\), or \(k>|C|\) do not invalidate the equivalence; they simply yield no-instances on both sides.

Verdict

No substantive error, missing lemma, or unjustified inference was found. The prover fully resolves the requested polynomial-time-versus-\(\mathrm{NP}\)-hard classification and additionally proves membership in \(\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩