d4-conf-atal-2015-0263 (d4-conf-atal-2015-0263)

Given a candidate set \(A\), a finite support \(\mathcal T\subseteq 2^A\), positive binary-rational masses \(\mu_P\) summing to \(1\), and a threshold \(\rho\), with \(\sum_{P\ni a}\mu_P=\tfrac12\) for each \(a\in A\), is there a committee \(S\subseteq A\) such that \(\max_{P\in\mathcal T} d_H(P,S)\le\rho\)?

Let \(A\) be a finite candidate set with \(m=|A|\). Approval types are arbitrary subsets of \(A\), including the empty set.
A society is given by its support: a nonempty list \(\mathcal T\subseteq 2^A\) of distinct types with positive binary-rational masses \(\mu_P\), summing to \(1\). Here \(\tau=|\mathcal T|\) is the support size, not the number of possible types.
Require balance: \(\sum_{P\in\mathcal T:a\in P}\mu_P=\tfrac12\) for every \(a\in A\). The threshold is \(\rho\in\mathbb Q\), encoded in binary.
A committee is any subset \(S\subseteq A\), with no cardinality restriction; empty and full committees are allowed. Write \(d_H\) for Hamming distance between approval sets.
Target. Is deciding whether there exists a committee \(S\) with \(\max_{P\in\mathcal T}d_H(P,S)\le\rho\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and the total input bit length \(L\).
Nearest known result. For an explicitly listed finite electorate, unrestricted minimax approval decision is \(\mathrm{NP}\)-complete even when every candidate is approved by exactly half the voters.

Result

The decision problem is \(\mathrm{NP}\)-complete. This holds even when every mass is dyadic, meaning its denominator is a power of two, and the threshold is \(\rho=m/2\).

We give a direct reduction, so the conclusion covers both interpretations of “binary-rational”: arbitrary rationals encoded in binary and finite binary fractions.

Balance gives a universal lower bound

For every committee \(S\), balance implies that its mass-weighted average distance is \(m/2\).

Indeed, a candidate in \(S\) contributes to the distance precisely for types that disapprove it, whose total mass is \(1/2\). A candidate outside \(S\) contributes precisely for types that approve it, again of total mass \(1/2\). Summing over candidates gives

\(\displaystyle \sum_{P\in\mathcal T}\mu_P d_H(P,S)=\frac m2.\)

Consequently, \(\max_{P\in\mathcal T}d_H(P,S)\ge m/2\). Moreover, since every mass is positive, a committee attaining maximum distance at most \(m/2\) must have distance exactly \(m/2\) from every supported type.

Thus thresholds below \(m/2\) are immediate no-instances. The reduction below shows that deciding feasibility exactly at this lower bound is already hard.

Reduction from satisfiability

We use the standard \(\mathrm{NP}\)-complete restriction of \(\mathrm{3SAT}\) in which every clause contains three literals on distinct variables.

Let the formula have \(n\) variables and \(c\) clauses. Introduce two additional Boolean variables \(s_j,t_j\) for each clause \(j\), and one additional variable \(h\). Let

\(\displaystyle q=n+2c+1.\)

For each of these \(q\) variables \(u\), create two candidates \(u^+\) and \(u^-\). Hence \(m=2q\). We will use threshold \(\rho=q=m/2\).

Associate a positive literal \(u\) with candidate \(u^+\), and a negative literal with candidate \(u^-\).

Ballots and masses

Construct the following multiset of ballots:

• For every variable \(u\), include \(E_u=\{u^+,u^-\}\) and its complement \(A\setminus E_u\).
• For each clause \(j\), whose literal candidates are \(a_{j1},a_{j2},a_{j3}\), include

\(\displaystyle F_j=\{a_{j1},a_{j2},a_{j3},s_j^-,t_j^-,h^-\}\)
and its complement \(A\setminus F_j\).

• Include \(\varnothing\) and \(A\).

Each \(F_j\) has six distinct candidates: the clause uses three distinct original variables, while its slack variables and \(h\) are fresh.

The multiset initially contains \(R=2(q+c+1)\) ballots. Let \(N\) be the smallest power of two satisfying \(N\ge R\). Since \(R\) and \(N\) are even, append \((N-R)/2\) further pairs \((\varnothing,A)\).

Now merge identical ballots. If type \(P\) occurs \(k_P\) times, assign it mass \(\mu_P=k_P/N\).

These masses are positive dyadic rationals and sum to one. Every ballot was introduced together with its complement. Therefore, each candidate appears in exactly one ballot of every complementary pair, and its approval mass is exactly \(1/2\). The constructed society satisfies balance.

Repeated ballots are merged, so the output really is a list of distinct supported types.

Consequences of feasibility

For every ballot \(P\) and committee \(S\),

\(\displaystyle d_H(P,S)+d_H(A\setminus P,S)=m=2q.\)

Both \(P\) and its complement occur in the support. Thus, if \(S\) is feasible at threshold \(q\), both distances must equal \(q\).

In particular, the empty ballot forces \(|S|=q\). For any ballot \(E\),

\(\displaystyle d_H(E,S)=|S|+|E|-2|E\cap S|=q+|E|-2|E\cap S|.\)

Since its distance equals \(q\), we obtain \(|E\cap S|=|E|/2\). Applying this to the constructed ballots gives:

• \(|E_u\cap S|=1\) for every variable \(u\);
• \(|F_j\cap S|=3\) for every clause \(j\).

Thus exactly one candidate from each variable pair is selected.

Also, complementing a feasible committee preserves feasibility: every supported distance is \(q\), and

\(\displaystyle d_H(P,A\setminus S)=2q-d_H(P,S)=q.\)

We may therefore assume \(h^+\in S\).

A feasible committee yields a satisfying assignment

Interpret \(u\) as true exactly when \(u^+\in S\). The pair constraints ensure that \(u^-\in S\) exactly when \(u\) is false, so selected literal candidates correspond precisely to true literals.

For clause \(j\), let \(r_j\) denote its number of true literals. Let \(s_j,t_j\in\{0,1\}\) denote the truth values assigned to its slack variables.

Because \(h^+\in S\), candidate \(h^-\) is absent. Consequently,

\(\displaystyle |F_j\cap S|=r_j+(1-s_j)+(1-t_j)=3.\)

Rearranging gives \(r_j=1+s_j+t_j\ge1\). Every clause therefore has a true literal, and the original formula is satisfiable.

A satisfying assignment yields a feasible committee

Conversely, suppose the formula is satisfiable. Set \(h\) to true. In each clause, its number \(r_j\) of true literals belongs to \(\{1,2,3\}\). Choose slack values satisfying \(s_j+t_j=r_j-1\), which is possible because the right-hand side belongs to \(\{0,1,2\}\).

Select exactly the candidate representing the truth value of each original, slack, and anchor variable. The resulting committee has size \(q\).

Each pair ballot contains exactly one selected candidate. Each clause ballot contains

\(\displaystyle r_j+(1-s_j)+(1-t_j)=3\)

selected candidates. The distance formula above therefore gives distance \(q\) from every pair ballot and every clause ballot. Their complements also have distance \(q\), as do \(\varnothing\) and \(A\).

Hence the committee is feasible. This proves both directions of the reduction.

Encoding size and running times

In the reduction, \(m=2(n+2c+1)\) and \(\tau\le R=2(n+3c+2)\). Padding introduces only types already present. Also, \(N<2R\), so every mass requires \(O(\log(R+1))\) bits.

Using incidence vectors, the output bit length is

\(\displaystyle L=O\!\left(m\tau+\tau\log(R+1)+\log(m+2)\right)=O((n+c+1)^2).\)

The construction, including sorting ballots and merging duplicates, takes \(O((n+c+1)^2\log(n+c+2))\) bit operations. It is therefore a polynomial-time reduction.

For a general valid input, a committee is an \(m\)-bit certificate. Compute \(\lfloor\rho\rfloor\) once using exact integer arithmetic, then scan the \(\tau\) types to compute their Hamming distances. With elementary arithmetic, verification takes

\(\displaystyle O\!\left(L^2+m\tau\log(m+2)\right)\)

bit operations. Positivity, normalization, distinctness, and balance are also checkable in \(\operatorname{poly}(L)\) time, if input validity must be verified. Thus the problem belongs to \(\mathrm{NP}\).

Enumerating all committees gives a deterministic algorithm with running time

\(\displaystyle O\!\left(L^2+2^m m\tau\log(m+2)\right)\)

on valid inputs, plus polynomial-time validation if required. No expansion of rational masses into individual voters is needed.

Combining membership with the reduction proves \(\mathrm{NP}\)-completeness. A polynomial-time algorithm in the total input length \(L\) would therefore imply \(\mathrm P=\mathrm{NP}\).

Relation to the supplied known result

For arbitrary binary-encoded rational masses, the supplied finite-electorate theorem also transfers directly: replace repeated ballots by their distinct types and assign mass equal to multiplicity divided by electorate size. Balance and every committee’s maximum distance are preserved, and the transformation has polynomial output size. The cited finite-electorate theorem is Theorem 1 of [*Multiple Referenda and Multiwinner Elections Using Hamming Distances*](https://aamas.csc.liv.ac.uk/Proceedings/aamas2015/aamas/p715.pdf).

The direct proof above additionally guarantees power-of-two denominators and establishes hardness at \(\rho=m/2\).

⟨structured verdict parsed — rendered above⟩

The output resolves the target correctly. The reduction establishes \(\mathrm{NP}\)-hardness for balanced societies with distinct supported types, dyadic masses, and threshold \(\rho=m/2\). The membership argument establishes \(\mathrm{NP}\)-completeness. I found no major or minor mathematical issues.

• Balance and the lower bound are correct.

For each candidate, its contribution to the mass-weighted distance is exactly \(1/2\), whether the committee includes it or excludes it. Summing these contributions gives
\[ \sum_{P\in\mathcal T}\mu_P d_H(P,S)=m/2. \]
Thus the maximum supported distance is at least \(m/2\).

The equality argument correctly uses strict positivity of every supported mass: if every distance is at most \(m/2\), any distance strictly below \(m/2\) would make the weighted average strictly smaller than \(m/2\). Therefore every supported distance must equal \(m/2\).

• The source problem and construction have the required hypotheses.

The stated source problem—satisfiability of formulas whose clauses contain exactly three literals on distinct variables—is a standard \(\mathrm{NP}\)-complete restriction of \(\mathrm{3SAT}\). The construction explicitly assumes this restriction.

The candidate count \(m=2q\), where \(q=n+2c+1\), is correct. The slack variables are fresh for each clause, and the anchor variable is fresh globally. Consequently, each clause ballot \(F_j\) contains exactly six distinct candidates, as required for the later intersection calculation.

There is no dependence on a committee-size restriction in the target problem: the reduction derives the committee size from supported ballots.

• Padding and merging produce a valid balanced support.

The initial ballot count is
\[ R=2(q+c+1)=2(n+3c+2). \]
Since \(q\ge1\), both \(R\) and the chosen power of two \(N\) are even. Hence the number \((N-R)/2\) of appended complementary pairs is a nonnegative integer.

Every occurrence belongs to a complementary pair. Each candidate therefore appears in exactly \(N/2\) occurrences, including after padding.

Merging duplicates preserves occurrence counts. The resulting masses \(k_P/N\) are positive, sum to one, and give approval mass exactly \(1/2\) to every candidate. Their denominators are powers of two, including after fraction reduction. The support is nonempty and contains distinct types.

Possible coincidences between constructed ballots cause no problem: merging retains every relevant supported type and preserves all distance constraints.

• The consequences of feasibility follow correctly.

The identity
\[ d_H(P,S)+d_H(A\setminus P,S)=2q \]
holds coordinate by coordinate. Both complementary types remain supported after merging. If both distances are at most \(q\), each must equal \(q\).

The empty ballot then forces \(|S|=q\). Substitution into the stated Hamming-distance formula correctly yields
\[ |E\cap S|=|E|/2 \]
for each supported ballot \(E\). Thus every variable-pair ballot forces exactly one selected candidate, and every clause ballot forces exactly three selected candidates.

Complementing the committee preserves all supported distances at \(q\). Together with the variable-pair constraint for \(h\), this justifies assuming \(h^+\in S\).

• The implication from feasibility to satisfiability is correct.

Selecting exactly one candidate from each variable pair makes the truth-value interpretation well-defined, including for negative literals.

With \(h^-\) absent, the clause intersection equation is correctly computed as
\[ r_j+(1-s_j)+(1-t_j)=3. \]
Rearrangement gives \(r_j=1+s_j+t_j\ge1\). This establishes satisfaction of every original clause.

The normalization by committee complementation is legitimate: the assignment is extracted from the normalized feasible committee, so the argument does not assume that complementing an assignment preserves satisfaction of the formula.

• The implication from satisfiability to feasibility is correct.

For a satisfying assignment, each \(r_j\) lies in \(\{1,2,3\}\). Boolean slack values can realize every required sum \(r_j-1\in\{0,1,2\}\). Their choices are independent because each clause has its own slack variables.

The resulting committee selects exactly one candidate per variable pair and therefore has size \(q\). Every pair ballot has intersection size one; every clause ballot has intersection size three. The distance formula consequently gives distance \(q\) for these ballots.

Complementary ballots, the empty ballot, and the full ballot also have distance \(q\). Padding and merging introduce no additional distance requirement. This proves the reverse implication.

• The encoding and running-time bounds are valid.

Padding adds only types already present, so \(\tau\le R\). The smallest-power-of-two choice gives \(N<2R\); both multiplicities and denominators therefore require \(O(\log(R+1))\) bits.

Under the explicitly stated incidence-vector representation, the claimed output-size bound
\[ L=O\!\left(m\tau+\tau\log(R+1)+\log(m+2)\right) =O((n+c+1)^2) \]
is correct. Constructing and sorting \(O(n+c+1)\) ballots of length \(O(n+c+1)\), then merging duplicates, fits the stated polynomial bit-operation bound.

For general valid inputs, an \(m\)-bit committee certificate suffices. Because Hamming distances are integers, comparison with \(\lfloor\rho\rfloor\) is exact, including for negative or nonintegral thresholds. The verification bound
\[ O\!\left(L^2+m\tau\log(m+2)\right) \]
is a valid conservative bound.

Exact validation of masses, normalization, distinctness, and balance is polynomial in \(L\), as claimed. Enumerating all committees gives the stated deterministic bound
\[ O\!\left(L^2+2^m m\tau\log(m+2)\right) \]
on valid inputs. The unrestricted inclusion of empty and full committees is respected. The case \(m=0\) creates no exception to membership or enumeration.

• The cited finite-electorate result and its transfer are correct.

The linked paper defines unrestricted minimax decision and balanced elections, and its Theorem 1 states the claimed \(\mathrm{NP}\)-completeness result. [Original paper](https://aamas.csc.liv.ac.uk/Proceedings/aamas2015/aamas/p715.pdf).

Aggregating repeated ballots into masses equal to multiplicity divided by electorate size preserves balance and every committee’s maximum distance. For an explicitly listed electorate, this transformation has polynomial size and running time.

The output correctly limits this transfer to arbitrary binary-encoded rationals. Its separate reduction establishes the stronger dyadic restriction without relying on that transfer.

No repair or additional clarification is needed. The proved conclusion is \(\mathrm{NP}\)-completeness, with the stated stronger restrictions and running-time bounds.

⟨structured verdict parsed — rendered above⟩