d4-conf-ecai-2025-0165 (d4-conf-ecai-2025-0165)

Given lexicographically ordered candidates \(C\), committee size \(k\), and approval types \(A\subseteq 2^C\) with positive rational masses \(\mu_A\) summing to \(1\), start with \(W_0=\varnothing\). At each round \(r\), add to \(W_r\) the lexicographically first candidate \(c\in C\setminus W_r\) maximizing \(\Delta_\mu(c\mid W_r)=\sum_{A:\,c\in A,\ A\cap W_r=\varnothing}\mu_A\). Compute \(W_k\), or decide whether a designated candidate belongs to it.

Let \(C\) be an explicitly listed, lexicographically ordered candidate set with \(m=|C|\geq 1\), let \(1\leq k\leq m\) be an integer, and let \(d\in C\).
A society is given by its support: a list \(\mathcal S\subseteq 2^C\) of \(\tau\) distinct approval types with positive binary rational masses \(\mu_A\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; empty approval types are allowed. Let \(L\) be the total input bit length.
Define mass sequential Chamberlin–Courant by \(W_0=\varnothing\). For \(0\leq r<k\), choose the lexicographically first candidate \(c\in C\setminus W_r\) maximizing \(\Delta_\mu(c\mid W_r)=\sum_{A\in\mathcal S:\,c\in A,\,A\cap W_r=\varnothing}\mu_A\), and set \(W_{r+1}=W_r\cup\{c\}\). Perform all \(k\) rounds, including rounds with zero marginal gain.
The decision problem asks whether \(d\in W_k\); the associated computation problem outputs \(W_k\). State running times in \(m,\tau,L,k\).

Is mass sequential Chamberlin–Courant candidate membership in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?

For explicitly listed discrete voters, sequential Chamberlin–Courant is polynomial-time computable, and candidate membership is \(\mathrm P\)-hard under logspace reductions, even when tie-breaking is never invoked. [Verified source](https://arxiv.org/html/2501.15006v3).
The verified source does not classify the normalized rational-mass support formulation.

Classification

Mass sequential Chamberlin–Courant candidate membership is in \(\mathrm P\). In fact, it is \(\mathrm P\)-complete under logspace many-one reductions. The associated computation problem is in \(\mathrm{FP}\).

Both problems admit the bit-operation running-time bound
\[ O\!\left(\tau L^2+m(\tau+k)L\right). \]
Thus candidate membership could be \(\mathrm{NP}\)-hard under polynomial-time reductions only if \(\mathrm P=\mathrm{NP}\).

1. Exact integer representation

Write each input mass as \(\mu_A=p_A/q_A\), where the positive integers \(p_A,q_A\) are encoded in binary. Define
\[ D=\prod_{A\in\mathcal S}q_A, \qquad w_A=p_A(D/q_A). \]

Each \(w_A\) is a positive integer, and normalization gives
\[ \sum_{A\in\mathcal S}w_A =D\sum_{A\in\mathcal S}\mu_A =D. \]

The bit length of \(D\) is at most one plus the sum of the bit lengths of the input denominators, hence is \(O(L)\). Because \(0<w_A\leq D\), every weight also has \(O(L)\) bits.

For every committee \(W\) and available candidate \(c\), define
\[ G(c\mid W) =\sum_{\substack{A\in\mathcal S\\c\in A,\ A\cap W=\varnothing}}w_A. \]
Then
\[ G(c\mid W)=D\,\Delta_\mu(c\mid W). \]

Since \(D>0\), the integer scores preserve all strict comparisons and all ties. Furthermore, \(0\leq G(c\mid W)\leq D\), so every score has \(O(L)\) bits.

Using schoolbook integer multiplication and division, constructing \(D\) and all weights takes \(O(\tau L^2)\) bit operations. The algorithm never needs to expand the masses into individual voters.

2. Algorithm and correctness

Maintain a selected-candidate flag, a covered-type flag, and an integer score \(g_c\) for each candidate. Initially set
\[ g_c=\sum_{A\in\mathcal S:\,c\in A}w_A. \]

Perform exactly \(k\) rounds:

• Scan the unselected candidates in their given lexicographic order. Choose a candidate with maximum score, retaining the first candidate when scores tie.
• Mark that candidate \(x\) selected.
• For each previously uncovered type \(A\) containing \(x\), mark \(A\) covered and subtract \(w_A\) from \(g_c\) for every still-unselected candidate \(c\in A\).

The invariant after round \(r\) is that a type \(A\) is covered precisely when \(A\cap W_r\neq\varnothing\), and that every unselected candidate satisfies
\[ g_c =\sum_{\substack{A\in\mathcal S\\c\in A,\ A\cap W_r=\varnothing}}w_A. \]

Initially, this follows from \(W_0=\varnothing\). Suppose it holds before selecting \(x\). A type changes from uncovered to covered exactly when it was previously uncovered and contains \(x\). For every remaining candidate, the update subtracts exactly the contributions of those newly covered types. Therefore the invariant holds after the round.

By Section 1, maximizing \(g_c\) with the stated tie-breaking is exactly the prescribed choice. Induction proves that the algorithm produces \(W_k\).

There is always an available candidate because \(r<k\leq m\). The algorithm continues even when all scores are zero, choosing the lexicographically first available candidate. Empty approval types contribute to no score and are handled without exception.

3. Running time

Use an incidence table recording whether each candidate belongs to each listed type. A conservative construction bound, including comparisons of encoded candidate names, is \(O(m\tau L)\) bit operations.

Initialization requires at most \(m\tau\) additions of \(O(L)\)-bit integers. The candidate scans require at most \(km\) comparisons of such integers.

Each type becomes covered at most once. Consequently, all score updates together require at most \(m\tau\) subtractions. Finding newly covered types by scanning the support each round requires \(k\tau\) incidence checks; since \(k\leq m\), this is at most \(m\tau\).

Including integer preprocessing, the total bound is therefore
\[ O\!\left(\tau L^2+m(\tau+k)L\right) \]
bit operations. This bound applies both to outputting \(W_k\) and to deciding whether \(d\in W_k\). Because the candidates and support are explicitly listed, their counts are bounded by the input length, so the bound is polynomial in \(L\).

4. Transfer of discrete-voter hardness

We use the supplied discrete-voter theorem: sequential Chamberlin–Courant candidate membership is \(\mathrm P\)-hard under logspace reductions, even on instances where tie-breaking is never invoked. This is established in Section 3.1 of [Fitzsimmons, Hassan, and Hemaspaandra](https://arxiv.org/html/2501.15006v3#S3.SS1).

Let a discrete election have explicitly listed voters with approval sets \(A_1,\ldots,A_n\). We may ensure \(n\geq1\) by adding one empty voter if necessary; an empty voter changes no marginal gain.

For each distinct approval set \(A\), let
\[ h_A=|\{i:A_i=A\}|, \qquad \mu_A=\frac{h_A}{n}. \]
Output the support consisting of those distinct sets, with these masses, and retain the candidates, their order, \(k\), and \(d\).

This is a valid target instance: all masses are positive, and
\[ \sum_A\mu_A=\frac{\sum_A h_A}{n}=1. \]

For every candidate \(c\) and committee \(W\),
\[ \Delta_\mu(c\mid W) =\frac1n |\{i:c\in A_i,\ A_i\cap W=\varnothing\}|. \]
Thus every mass marginal is the corresponding discrete marginal multiplied by the same positive factor. All comparisons and ties are preserved, so induction over the rounds shows that the entire selection sequence is identical. In particular, candidate membership is preserved, and instances with unique maximizing candidates retain that property.

The conversion is computable in logspace. For each voter position \(i\), repeated scans determine whether its approval set occurred earlier. If not, further scans count its multiplicity and output the set with mass \(h_A/n\). Equality of approval sets can be checked by scanning the candidates and comparing membership. Only a constant number of input-position counters and counts are needed, each using logarithmic space. If reduced fractions are required, their greatest common divisor can also be computed using logarithmic space.

Hence discrete-voter membership logspace-reduces to normalized rational-mass membership. Combined with the polynomial-time algorithm, this proves \(\mathrm P\)-completeness.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output correctly establishes candidate membership in \(\mathrm P\), computation in \(\mathrm{FP}\), and the stronger claim of \(\mathrm P\)-completeness under logspace many-one reductions. The stated running-time bound is valid. No major or minor mathematical issues were found.

1. Exact integer representation

The construction uses positive integer denominators, so \(D=\prod_{A\in\mathcal S}q_A\) is positive and each quotient \(D/q_A\) is an integer. Consequently, every \(w_A=p_A(D/q_A)\) is a positive integer.

The normalization calculation is correct:
\[ \sum_{A\in\mathcal S}w_A=D. \]
It implies \(w_A\leq D\), including when input fractions are not reduced.

The bit-length bound is valid. The logarithm of a product is the sum of the logarithms of its factors, and the denominator encodings are part of \(L\). Thus \(D\), every weight, and every score have \(O(L)\) bits. The proof does not confuse the potentially large numerical value of \(D\) with its encoding length.

The identity \(G(c\mid W)=D\,\Delta_\mu(c\mid W)\) follows directly from the definitions. Multiplication by the same positive constant preserves both strict comparisons and equality, so the argument correctly preserves lexicographic tie-breaking.

There are \(O(\tau)\) multiplications and divisions on integers of \(O(L)\) bits. The schoolbook bound \(O(\tau L^2)\) therefore holds. No expansion into individual voters is needed.

2. Algorithm and invariant

The initialization gives precisely the required scores for \(W_0=\varnothing\). All types are initially uncovered, consistent with the stated invariant.

The inductive update is correct. A previously uncovered type becomes covered exactly when it contains the newly selected candidate \(x\). Its contribution must then disappear from the score of every remaining candidate it contains. The prescribed subtraction does exactly this.

Selected candidates need not have their scores maintained, because subsequent scans exclude them. Each type is marked covered before it could be processed again, so its weight is subtracted only once from each relevant remaining score. The invariant also ensures that these subtractions do not produce negative scores.

Scanning candidates in the given order and retaining the first maximizer implements the specified tie-breaking. Together with the integer-score identity, the induction proves agreement with the prescribed selection sequence for all \(k\) rounds.

3. Domain restrictions and edge cases

The proof addresses the relevant cases correctly:

• Before every round, \(r<k\leq m\), so an unselected candidate exists.
• Zero scores do not terminate the algorithm; the first available candidate is selected.
• Empty approval types remain uncovered and contribute to no candidate score, exactly as required.
• The cases \(m=1\) and \(k=m\) require no modification.
• Normalization and positive masses imply that the support is nonempty, so no unsupported empty-support case arises.

The proof uses the task’s explicitly listed support representation throughout. It does not assume that all possible approval types are listed.

4. Running-time accounting

The incidence-table construction bound \(O(m\tau L)\) is conservative and sufficient for explicitly encoded candidate names and approval sets.

The remaining operation counts are correct:

• Initialization uses at most \(m\tau\) integer additions.
• Winner selection uses at most \(km\) integer comparisons.
• Each type becomes covered at most once, giving at most \(m\tau\) score subtractions overall.
• Scanning the support in every round uses \(k\tau\) incidence checks, bounded by \(m\tau\).

All score arithmetic involves \(O(L)\)-bit integers. Combining these costs with integer preprocessing gives
\[ O\!\left(\tau L^2+m(\tau+k)L\right). \]

Outputting the selected candidate names is also covered by this bound, since those names are already explicitly present in the input. Because \(m\), \(\tau\), and \(k\) are bounded by the explicit input length, this is polynomial in \(L\).

5. Cited discrete-voter hardness theorem

The cited result matches the required source problem. Section 3.1 defines sequential Chamberlin–Courant using lexicographic tie-breaking, establishes candidate-membership hardness under logspace reductions, and gives the strengthening that tie-breaking need never be invoked. The theorem being used is also expressly supplied by the task. [Verified source, Section 3.1](https://arxiv.org/html/2501.15006v3#S3.SS1).

The prover therefore invokes an applicable theorem, rather than assuming that hardness of an unrelated committee rule transfers.

6. Reduction to normalized rational support

Grouping identical approval sets gives distinct support types with positive multiplicities \(h_A\). For \(n\geq1\), the masses \(h_A/n\) are positive binary-encoded rationals and sum to one. Candidate identities, order, committee size, and distinguished candidate are retained.

The displayed marginal identity is correct:
\[ \Delta_\mu(c\mid W)=\frac1n |\{i:c\in A_i,\ A_i\cap W=\varnothing\}|. \]
It applies to every candidate and every intermediate committee. Hence the entire sequence, including ties and zero-gain rounds, is preserved. Unique maximizers remain unique.

Adding an empty voter when the original voter list is empty changes no discrete marginal gain and makes normalization possible. The subsequent construction is understood to use the resulting positive voter count.

The logspace argument is sufficient. First-occurrence detection, multiplicity counting, and set-equality checks use repeated input scans and a constant number of logarithmic-size counters. No collection of all distinct types must be stored. The output has polynomial length. The optional fraction-reduction claim is also valid because the numerator and denominator here have logarithmic bit length in the discrete input size.

7. Final classification and repair requirements

The polynomial-time algorithm establishes the requested classification independently of the hardness transfer. The valid logspace reduction supplies the additional \(\mathrm P\)-completeness result.

The qualification concerning \(\mathrm{NP}\)-hardness is correct: polynomial-time many-one \(\mathrm{NP}\)-hardness of this problem would imply \(\mathrm P=\mathrm{NP}\).

No additional clarification, missing lemma, or repair is required.

⟨structured verdict parsed — rendered above⟩