d4-conf-aaai-2026-1451 (d4-conf-aaai-2026-1451)

Given candidates \(C\), a committee size \(k\), and \(\tau\) approval types \(A_t\subseteq C\) with positive binary-rational masses \(\mu_t\) summing to \(1\), suppose the types have an order in which each candidate is approved by consecutive types. For a fixed Thiele sequence \(w\), can an optimal size-\(k\) committee maximizing \(S_\mu(W)=\sum_t\mu_t\sum_{i=1}^{|A_t\cap W|}w_i\) be computed in time \(f(\rho_C+\rho_V)\operatorname{poly}(m,\tau,L)\), where \(\rho_C=\max_c|\{t:c\in A_t\}|\), \(\rho_V=\max_t|A_t|\), and \(L\) is the total mass bit length?

Fix a Thiele sequence \(w\) with \(1=w_1\geq w_2\geq\cdots\geq0\), whose first \(m\) entries are binary rationals computable in polynomial time in \(m\).
A society is given by its support: \(\tau\) distinct approval sets \(A_t\subseteq C\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible approval sets; \(L\) is the total mass bit length.
Let \(m=|C|\geq1\), \(1\leq k\leq m\), and require every candidate to have a supporter; empty approval sets are allowed. The support admits a linear order in which each candidate's supporting types are consecutive.
Define \(\rho_C=\max_{c\in C}|\{t:c\in A_t\}|\) and \(\rho_V=\max_t|A_t|\). Output any committee \(W\subseteq C\) of size \(k\) maximizing \(S_\mu(W)=\sum_{t=1}^{\tau}\mu_t\sum_{i=1}^{|A_t\cap W|}w_i\), with an empty inner sum equal to zero.

Is this optimization problem solvable in \(\operatorname{poly}(m,\tau,L,k)\) time, or is it \(\mathrm{NP}\)-hard? If it is \(\mathrm{NP}\)-hard, is it nevertheless solvable in \(f(\rho_C+\rho_V)\operatorname{poly}(m,\tau,L,k)\) time?

For discrete voter-interval elections, generalized Thiele winner determination is FPT in the sum of maximum candidate support and maximum ballot size, and XP in maximum candidate support; unrestricted nonconstant Thiele rules are NP-hard and W[1]-hard in committee size. [Lassota–Sornat](https://arxiv.org/html/2607.28575v1)
Later polynomial-time results explicitly cover voter-interval elections with arbitrary binary-rational, voter-specific non-increasing scoring sequences, including this mass objective. Thus the stated target is already settled in \(\mathrm{P}\), rather than open. [Manurangsi–Sornat](https://arxiv.org/html/2604.05953v1)

Conclusion

The problem is solvable in \(\operatorname{poly}(m,\tau,L,k)\) time for every fixed sequence \(w\) satisfying the stated assumptions. Consequently, it is also fixed-parameter tractable in \(\rho_C+\rho_V\), with a constant parameter factor.

The proof is a polynomial-size reduction to generalized Thiele winner determination on voter-interval profiles.

The theorem used

Manurangsi–Sornat, Theorem 10. Given a voter-interval approval profile and voter-specific, nonnegative, non-increasing scoring sequences with entries in \([0,1]\), encoded as binary rationals, an optimal committee of the prescribed size can be computed in polynomial time in the input encoding length. Individual sequences need not have first entry equal to \(1\). Their formulation supplies the first \(m\) entries of each sequence. See [Section 2 and Theorem 10](https://arxiv.org/html/2604.05953v1).

We apply this theorem directly, checking the objective, structural assumptions, and encoding size below.

Reduction and correctness

Let \(T=\{t:A_t\neq\varnothing\}\). Construct one voter \(v_t\) for every \(t\in T\), with approval ballot \(A_t\). Keep the candidate set \(C\) and required committee size \(k\).

For each constructed voter, supply the scoring entries
\[ a_i^{\,t}=\mu_t w_i,\qquad 1\leq i\leq m. \]
If an infinite sequence is desired, extend these entries by zeros after position \(m\).

Scoring hypotheses. Positivity of the masses and their normalization imply \(0<\mu_t\leq1\). Therefore
\[ 1\geq a_1^{\,t}\geq a_2^{\,t}\geq\cdots\geq a_m^{\,t}\geq0. \]
Thus every constructed sequence meets the theorem’s hypotheses. In particular, its first entry is \(\mu_t\), which the generalized formulation permits.

Voter-interval hypothesis. Take the promised order of the original types and restrict it to \(T\). For any candidate, its supporters remain consecutive: if two retained types support it, every retained type between them also lay between them in the original order and hence supports it. Moreover, deleting empty types removes no supporter. Thus every candidate still has a supporter, and the constructed profile is voter-interval.

Objective preservation. For every committee \(W\subseteq C\),
\[ \sum_{t\in T}\sum_{i=1}^{|A_t\cap W|}a_i^{\,t} =\sum_{t\in T}\mu_t\sum_{i=1}^{|A_t\cap W|}w_i =S_\mu(W). \]
The final equality holds because each omitted empty approval set contributes zero. The feasible committees also remain exactly the size-\(k\) subsets of \(C\). Consequently, an optimal committee returned for the constructed instance is optimal for the original society.

Encoding size and running time

Let \(B_w(m)\) be the total bit length of the first \(m\) entries of \(w\). The assumed polynomial-time computation of those entries implies that \(B_w(m)\) is polynomially bounded in \(m\).

Write \(\mu_t=p_t/q_t\) and \(w_i=r_i/s_i\), using their binary-rational representations. We can encode
\[ a_i^{\,t}=\frac{p_t r_i}{q_t s_i}. \]
The numerator and denominator lengths are bounded by the sums of the corresponding input lengths, up to a constant. Reduction to lowest terms can only decrease these lengths.

Summing over all constructed entries, their total encoding length is therefore
\[ O\!\left(mL+\tau B_w(m)+\tau m\right). \]
The approval profile has at most \(\tau\) voters and can be represented by an incidence matrix with \(\tau m\) entries. All rational products are computable in polynomial time.

Hence the constructed input has size polynomial in \(m,\tau,L,k\). Applying Theorem 10 proves the required polynomial running time. This construction uses one voter per retained support type; the masses enter only through the scoring coefficients.

Parameterized consequence

The same algorithm has running time \(f(\rho_C+\rho_V)\operatorname{poly}(m,\tau,L,k)\) with \(f(p)=1\). Thus the parameterized question is settled affirmatively without needing a hardness assumption.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The cited theorem applies to the constructed instance, the reduction preserves the objective exactly, and the encoding remains polynomial. No major or minor mathematical issues were found.

• The cited theorem is stated accurately.

Manurangsi–Sornat’s Theorem 10 gives a polynomial-time algorithm for Generalized Thiele on voter-interval profiles. Section 2 specifies voter-specific non-increasing sequences taking values in \([0,1]\), with the first \(m\) entries supplied as binary-encoded rational numerators and denominators. It explicitly permits first entries different from \(1\). The computational problem requires finding a winning committee, so the theorem supplies the requested optimizer rather than merely its score. [Section 2 and Theorem 10](https://arxiv.org/html/2604.05953v1)

• The constructed instance satisfies the scoring hypotheses.

For each retained type, \(0<\mu_t\leq1\) follows from positivity and normalization. Multiplying the original inequalities by \(\mu_t\) gives
\(1\geq a_1^{\,t}\geq\cdots\geq a_m^{\,t}\geq0\).
Each entry is rational. Extending the sequence by zeros preserves nonnegativity and monotonicity, including at the transition after position \(m\). No normalization of each voter’s first entry is necessary.

• The candidate set and interval promise are preserved.

Every candidate originally has a supporter, and a supporting type cannot have an empty approval set. Deleting empty types therefore leaves every candidate supported and preserves the entire candidate set.

The argument about restricting the promised order is valid: every retained type between two supporters was also between them in the original order and hence supports the candidate. Thus the constructed profile is voter-interval. The order need not be supplied in the original input: the cited theorem concerns voter-interval profiles defined by existence of such an order, and the paper explicitly addresses finding the order. [Section 2](https://arxiv.org/html/2604.05953v1)

• Objective preservation is exact for every feasible committee.

Substitution of \(a_i^{\,t}=\mu_t w_i\) establishes the first equality in the displayed objective calculation. Restoring omitted empty types adds only zero terms. Neither the candidates nor the committee-size constraint changes, so the feasible committees coincide. Consequently, optimality transfers exactly, including ties and committees for which some voters approve no selected candidate.

• The encoding and construction bounds are correct.

Polynomial-time computation of the first \(m\) rational entries entails polynomial total output length \(B_w(m)\) under the stated explicit binary encoding.

Binary multiplication gives product numerators and denominators with lengths bounded by the sums of the operand lengths, up to a constant. Summing across retained types and indices yields the claimed bound
\(O(mL+\tau B_w(m)+\tau m)\).
An incidence-matrix representation adds at most \(\tau m\) entries. Exact rational arithmetic and optional fraction reduction take polynomial time. Thus applying the theorem incurs no dependence on the numerical magnitudes of denominators beyond their bit lengths.

• Boundary cases and the parameterized consequence are covered.

The retained voter set is nonempty because \(m\geq1\) and every candidate has a supporter. The cases \(m=1\) and \(k=m\) are valid instances; the unique size-\(m\) committee is the whole candidate set. Zero scoring entries cause no hypothesis violation.

The established polynomial-time algorithm immediately has the requested parameterized running time with \(f(p)=1\). This correctly answers the parameterized question without requiring a hardness premise.

Repair feedback: None is required. The output resolves the assigned optimization and parameterized-complexity questions.

⟨structured verdict parsed — rendered above⟩