d4-conf-ecai-2016-0060 (d4-conf-ecai-2016-0060)

Given a finite candidate set \(C\), target \(c\), a finite support \(T\) of complete rankings of \(C\), and positive rational masses \(\mu_t\) summing to \(1\), is there a partition \(C=C_1\mathbin{\dot\cup}C_2\) such that the mass-based veto subelections, with the specified TE or TP rule, promote finalists who make \(c\) a winner of the runoff under the specified unique-winner or nonunique-winner model? In each subelection and the runoff, restrict rankings to the candidates present and compute veto scores from the original society’s mass.

Given a nonempty candidate set \(C\), let \(m=|C|\) and designate \(c\in C\). A society is given by its support: a list \(T\) of \(\tau\) distinct complete strict rankings of \(C\), each with a positive binary rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
For each candidate subset, use veto with rankings restricted to that subset and scores weighted by the original masses. All maximum-score candidates are winners; a singleton elects its candidate and an empty election has no winners.
Fix one of TE (promote only a unique subelection winner) or TP (promote every subelection winner), and one of the unique-winner or nonunique-winner models. These choices define four separate decision problems.
A control action partitions \(C=C_1\mathbin{\dot\cup}C_2\), allowing empty parts and imposing no size constraint. Hold both subelections with the entire society, then hold a veto runoff on the union of their promoted candidates, again with the entire society and restricted rankings.
The decision question is whether some partition makes \(c\) the sole runoff winner in the unique-winner model, or a runoff winner in the nonunique-winner model.

For each of the four fixed model combinations, is this mass-based constructive control problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For finite unweighted societies, constructive control by runoff partition under TE is \(\mathrm{NP}\)-complete in both winner models, and under TP in the unique-winner model. The [full version](https://comsoc-community.org/assets/theses/phd-maushagen.pdf) establishes \(\mathrm{NP}\)-completeness also for TP in the nonunique-winner model.
No result explicitly classifying the normalized binary-rational mass formulation was located in the literature search.

Classification

All four problems are \(\mathrm{NP}\)-complete.

| Tie handling | Winner model | Complexity |
|---|---|---|
| TE | Unique winner | \(\mathrm{NP}\)-complete |
| TE | Nonunique winner | \(\mathrm{NP}\)-complete |
| TP | Unique winner | \(\mathrm{NP}\)-complete |
| TP | Nonunique winner | \(\mathrm{NP}\)-complete |

Thus, a running time polynomial in \(m,\tau,L\) exists for any of these problems if and only if \(\mathrm{P}=\mathrm{NP}\).

The singleton case \(m=1\) is always a yes-instance. The classification concerns unrestricted candidate sets. Rational masses are represented by binary-encoded integer numerators and denominators.

1. Normalization preserves every restricted election

Let \(V\) be a nonempty explicitly listed unweighted society with \(N\) voters. Let \(T\) contain precisely its distinct rankings, and let \(n_t\) be the number of voters having ranking \(t\). Define \(\mu_t=n_t/N\).

These masses are positive and satisfy \(\sum_{t\in T}\mu_t=1\).

Fix any nonempty candidate subset \(S\subseteq C\). For \(x\in S\), define \(I_{t,S}(x)\) to equal zero when \(x\) is last in the restriction of \(t\) to \(S\), and one otherwise. The unweighted and mass-based veto scores are respectively

\(\operatorname{score}_{V,S}(x)=\sum_{t\in T}n_t I_{t,S}(x)\)

and

\(\operatorname{score}_{\mu,S}(x)=\sum_{t\in T}(n_t/N)I_{t,S}(x)=\operatorname{score}_{V,S}(x)/N\).

Because \(N>0\), this identity preserves every strict score comparison and every score equality. Hence the two elections have exactly the same winner set on every nonempty \(S\). For a singleton, its sole candidate wins in both formulations; an empty election has no winners.

Now fix a partition \(C=C_1\mathbin{\dot\cup}C_2\). The subelection winner sets coincide under the two representations. Consequently, their promoted sets coincide under either TE or TP. Their runoff candidate sets therefore coincide, and the same score identity applies to the runoff.

Thus every partition succeeds in the unweighted instance exactly when it succeeds in the normalized mass instance, in either winner model.

2. Polynomial-time reduction and hardness

The finite-society hardness theorem stated in the question is Theorem 5(1) of the Maushagen–Rothe paper reproduced in the linked dissertation. It establishes \(\mathrm{NP}\)-completeness for constructive veto control by runoff partition under both tie-handling rules and both winner models. Its definitions use complete strict rankings, the entire society in both subelections and the runoff, and rankings restricted to each election’s candidate set. These are the required hypotheses. [Source: definitions and Theorem 5(1)](https://comsoc-community.org/assets/theses/phd-maushagen.pdf#page=38)

For each fixed combination, transform a finite-society instance by keeping \(C\) and \(c\), grouping identical rankings, and assigning the masses \(n_t/N\).

This transformation is polynomial-time:

• Grouping explicitly listed rankings and counting their multiplicities takes polynomial time in the source input length.
• There are \(\tau\leq N\) distinct rankings.
• Each numerator \(n_t\) and denominator \(N\) uses \(O(\log(N+1))\) bits.
• Reducing the fractions, if required by the encoding, takes polynomial time.

Therefore the resulting input has polynomial length. Section 1 proves the necessary equivalence of yes-instances and no-instances.

The allowance of empty parts creates no mismatch. In particular, the cited hardness construction uses nonempty societies and has a unique full-election winner \(w\neq c\). Its score difference is \(\operatorname{score}(w)-\operatorname{score}(c)=q-1>0\), where \(q>1\) is the number of source clauses. [Source: construction and full-election scores](https://comsoc-community.org/assets/theses/phd-maushagen.pdf#page=47) For either partition with an empty part, the nonempty subelection consequently promotes only \(w\), under both TE and TP. Such a partition cannot elect \(c\).

It follows that each of the four mass-based problems is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions.

3. Polynomial-time certificate verification

A certificate assigns each candidate to one of the two parts, using \(m\) bits. We show that its success can be checked with exact arithmetic in time polynomial in \(m,\tau,L\).

Write each input mass as \(\mu_t=a_t/b_t\), with positive integers \(a_t,b_t\). Set

\(D=\prod_{t\in T}b_t\), and \(W_t=a_t(D/b_t)\).

These are positive integers, and normalization gives \(\sum_{t\in T}W_t=D\). Moreover,

\(\log_2 D=\sum_{t\in T}\log_2 b_t=O(L)\).

Thus \(D\), all \(W_t\), and all partial sums of these positive weights have \(O(L)\) bits. They can be computed by polynomial-time integer arithmetic.

For a nonempty subset \(S\), scan each ranking to find its last candidate belonging to \(S\). For each \(x\in S\), compute the integer veto total

\(B_S(x)=\sum_{\{t:\,x\text{ is last in }t|_S\}}W_t\).

The mass-based score is \(1-B_S(x)/D\). Therefore the winners are exactly the candidates minimizing \(B_S(x)\), and uniqueness is determined by exact integer equality. This also handles singletons correctly.

Apply this computation to the two parts, form the promoted set according to TE or TP, and compute its runoff winners. Handle empty sets by returning no winners. Finally, check whether the winner set equals \(\{c\}\), or contains \(c\), as required.

Each election requires at most \(O(\tau m)\) ranking inspections and polynomially many operations on \(O(L)\)-bit integers. Hence the certificate verifier runs in polynomial time, proving membership in \(\mathrm{NP}\) for all four problems.

4. Conclusion

Normalization and aggregation give a polynomial-time reduction preserving every partition’s outcome. Exact integer score comparisons give polynomial-time certificate verification. Together these establish \(\mathrm{NP}\)-completeness for all four combinations.

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves all four problems. The normalization reduction preserves every partition’s outcome, the cited hardness theorem applies to the required election models, and the exact-arithmetic verifier establishes membership in \(\mathrm{NP}\). No substantive or minor mathematical gaps were found.

1. Scope and classification

The prover addresses all four combinations separately through arguments that apply uniformly to TE and TP, and to both winner models. Its stronger conclusion of \(\mathrm{NP}\)-completeness answers the requested classification.

The claim about polynomial running time is also correct: because the input explicitly lists its candidates, supported rankings, and rational masses, polynomial time in \(m,\tau,L\) is equivalent here to polynomial time in the input length.

2. Preservation under normalization

Every step in Section 1 is valid.

• The assumption \(N>0\) makes \(\mu_t=n_t/N\) well-defined. Including precisely the rankings that occur ensures \(n_t>0\), so every output mass is positive.
• Aggregation produces distinct support rankings, and their masses sum to one.
• For every nonempty subset \(S\), the indicator \(I_{t,S}(x)\) correctly represents the veto contribution of ranking \(t\).
• The displayed score identity follows by factoring out \(1/N\). This factor is positive and independent of the candidate, so it preserves all score comparisons and ties.
• Consequently, the entire winner set is preserved, including whether it contains exactly one candidate. This is sufficient for both promotion rules.
• For each fixed partition, preservation of the subelection winner sets implies preservation of the promoted union. Applying the same identity to that union preserves the runoff winners.

The quantification over every candidate subset is sufficient: it covers both parts and whichever runoff set results from the partition.

Singletons and empty elections are handled correctly. A singleton’s veto score is zero, but its candidate is nevertheless the unique maximum-score candidate. An empty runoff cannot satisfy either constructive objective.

3. Hardness theorem and reduction

The cited theorem is accurately stated. Theorem 5(1) establishes \(\mathrm{NP}\)-completeness of constructive veto control by runoff partition under both tie rules and both winner models. The source definitions use strict rankings, the full electorate in each round, restricted rankings, and unrestricted part sizes. These match the required hypotheses. [Definitions and Theorem 5(1)](https://comsoc-community.org/assets/theses/phd-maushagen.pdf)

The encoding argument is sound. With explicitly listed voters, grouping rankings and counting their occurrences is polynomial in the source input length. There are at most \(N\) groups, and each fraction \(n_t/N\) requires \(O(\log(N+1))\) bits. Fraction reduction, if required, is polynomial-time. The resulting support representation therefore has polynomial length.

The empty-part argument is also justified. The cited construction has a nonempty electorate and a unique full-election winner \(w\ne c\). Its displayed scores give the claimed difference \(q-1>0\), with the prover’s \(q\) corresponding to the source’s clause count. The scores of the variable candidates are strictly below \(w\)’s. [Construction and scores](https://comsoc-community.org/assets/theses/phd-maushagen.pdf#page=48)

Thus an empty-part partition promotes only \(w\), and its singleton runoff cannot elect \(c\). Allowing empty parts introduces no additional successful partitions on the hardness instances.

The polynomial reduction and its yes/no equivalence establish hardness for each fixed combination.

4. Exact-arithmetic verification

Section 3 correctly controls both arithmetic precision and running time.

• The product \(D=\prod_t b_t\) is divisible by every denominator, so every \(W_t=a_t(D/b_t)\) is an exactly computable positive integer.
• Normalization implies \(\sum_t W_t=D\).
• The total binary length of the denominators bounds \(\log_2 D\) by \(O(L)\). Since the weights are positive and sum to \(D\), each weight and each partial sum also has \(O(L)\) bits.
• Finding the last member of a nonempty subset in each complete ranking requires at most \(O(\tau m)\) ranking inspections.
• The score formula \(1-B_S(x)/D\) is correct because the total mass is one. Minimizing the veto total therefore identifies exactly all winners, with ties determined by exact integer equality.
• Repeating this computation for two subelections and one runoff requires only a constant number of polynomial-time computations.

The certificate uses \(m\) bits and represents every allowed partition, including partitions with an empty part. The final winner-set tests correctly distinguish the two winner models.

Input validity is stipulated by the task, so the verifier need not separately prove normalization or ranking validity.

5. Verdict and feedback

All four claimed classifications follow. No missing lemma, false computation, invalid theorem application, or unresolved edge case was identified. No additional mathematical clarification is needed.

⟨structured verdict parsed — rendered above⟩