d4-conf-ecai-2020-0025 (d4-conf-ecai-2020-0025)

Given a candidate set \(A\), committee size \(k\), and a finite support \(T\) of pairs of rankings over \(A\), with rational masses \(\mu_t\ge 0\) summing to \(1\), define \(b_{t,z}(S)=\sum_{c\in S}(m-r_{t,z}(c))\), where \(r_{t,z}(c)\) is candidate \(c\)'s position in type \(t\)'s ranking for layer \(z\in\{1,2\}\). Given a rational threshold \(q\), is there an integral committee \(S\subseteq A\), \(|S|=k\), such that \(\sum_{t\in T}\mu_t\max_{z\in\{1,2\}}b_{t,z}(S)\ge q\)?

Let \(A\) contain \(m\ge 1\) candidates, let \(1\le k\le m\) be an integer, and let \(q\in\mathbb{Q}\).
A society is given by its support: a list \(T\) of \(\tau\) distinct types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Each type specifies two strict complete rankings of \(A\); \(\tau\) is the support size, not the number of possible ranking pairs.
For \(z\in\{1,2\}\), let \(r_{t,z}(c)\in\{1,\ldots,m\}\) be the position of \(c\), with position \(1\) best. For an integral committee \(S\subseteq A\), define \(b_{t,z}(S)=\sum_{c\in S}(m-r_{t,z}(c))\).
The decision problem asks whether some \(S\subseteq A\) with \(|S|=k\) satisfies \(\sum_{t\in T}\mu_t\max_{z\in\{1,2\}}b_{t,z}(S)\ge q\). Any committee meeting the threshold is admissible; no tie-breaking is imposed.
Let \(L\) be the total binary input length; state running times in \(m,\tau,k,L\).

Is this rational-mass committee decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For an explicitly listed finite electorate, Max-\(k\)-Borda is \(\mathrm{NP}\)-hard and \(\mathrm{W}[1]\)-hard parameterized by \(k\), even with two layers. [Source](https://ecai2020.eu/papers/846_paper.pdf)
No separately stated complexity result for exactly the normalized rational-mass formulation was located in the search.

Result and source theorem

The problem is \(\mathrm{NP}\)-complete. Hardness holds even when every mass is dyadic, meaning its denominator is a power of two.

We use the following known result: given an explicitly listed electorate in which every voter supplies two strict complete rankings, deciding whether a size-\(k\) committee has total Max-\(k\)-Borda score at least an integer threshold \(R\) is \(\mathrm{NP}\)-hard and \(\mathrm{W}[1]\)-hard parameterized by \(k\). The paper defines Borda scores as \(m-r(c)\) and takes each voter’s maximum over layers, exactly as here. See Definition 1 and Theorem 1 of [Jain and Talmon, *Committee Selection with Multimodal Preferences*](https://ecai2020.eu/papers/846_paper.pdf).

Polynomial reduction to normalized masses

Consider an instance of that decision problem with \(n\ge 1\) explicitly listed voters. For a committee \(S\), write its unnormalized score as
\(H(S)=\sum_{v=1}^{n}\max_{z\in\{1,2\}}\sum_{c\in S}(m-r_{v,z}(c))\).

Ordinarily, grouping identical ranking pairs and assigning each group its fraction of voters immediately gives normalized rational masses. The following padding additionally ensures dyadic masses.

Duplicate every original voter once. Let \(N\) be the smallest power of two satisfying \(N\ge 2n\), and put \(p=(N-2n)/2\). Since \(N\) and \(2n\) are even, \(p\) is a nonnegative integer.

Choose any strict ranking \(\pi\) of the candidates, and let \(\pi^{\mathrm{rev}}\) be its reverse. Add \(p\) pairs of voters, where:

• The first voter in each pair uses \(\pi\) in both layers.
• The second uses \(\pi^{\mathrm{rev}}\) in both layers.

For every candidate \(c\), the positions satisfy
\(r_{\pi^{\mathrm{rev}}}(c)=m+1-r_\pi(c)\). Consequently,
\((m-r_\pi(c))+(m-r_{\pi^{\mathrm{rev}}}(c))=m-1\).

Each padding voter has identical layers, so its maximum equals its ordinary Borda committee score. Thus every padding pair contributes exactly \(k(m-1)\) to every size-\(k\) committee. The padded electorate therefore gives \(S\) total score
\(2H(S)+pk(m-1)\).

Group this electorate by its ordered pairs of rankings. For each resulting distinct type \(t\), let \(a_t\) be its positive multiplicity and set
\(\mu_t=a_t/N\).
These masses are positive dyadic rationals and sum to one. Set
\(q=(2R+pk(m-1))/N\).

The resulting normalized objective satisfies
\(F(S)=(2H(S)+pk(m-1))/N\). Since \(N>0\), we have the exact equivalence
\(F(S)\ge q\) if and only if \(H(S)\ge R\).
This holds for every size-\(k\) committee, including equality at the threshold; no tie-breaking condition enters the reduction.

All rankings remain strict and complete. Grouping makes the listed types distinct, including when a padding type coincides with an original type. Moreover, \(N<4n\), the support size satisfies \(\tau\le n+2\), and all new multiplicities and denominators have \(O(\log(n+1))\) bits. The threshold also has polynomial encoding length. Hence constructing and grouping the padded electorate takes polynomial time in the explicitly listed source input length.

This proves \(\mathrm{NP}\)-hardness. Because the reduction preserves \(k\), it also transfers \(\mathrm{W}[1]\)-hardness parameterized by \(k\).

Membership in \(\mathrm{NP}\) and exact verification

A certificate lists the \(k\) selected candidates. Check that they are distinct and belong to \(A\), and compute
\(u_t=\max_{z\in\{1,2\}}\sum_{c\in S}(m-r_{t,z}(c))\)
for every type. These integers satisfy \(0\le u_t\le k(m-1)\).

Write \(\mu_t=a_t/d_t\) and \(q=h/d_q\), with positive denominators. Define
\(D=d_q\prod_{t\in T}d_t\).
Then the threshold condition is precisely the integer comparison
\(\sum_{t\in T}a_t(D/d_t)u_t\ge h(D/d_q)\).

The bit length of \(D\) is at most the sum of the input denominator bit lengths, hence \(O(L)\). All integers in this comparison also have \(O(L)\) bits: the score numerators are bounded by \(Dk(m-1)\), and the threshold numerator has polynomially bounded bit length directly from its encoding.

Using elementary integer arithmetic and preprocessing the rankings into position tables, a safe verification bound is
\(O((\tau m+\tau k+1)L^2)\)
bit operations. Thus verification is polynomial, proving membership in \(\mathrm{NP}\).

Running times for restricted parameters

For completeness, enumerating committees gives an exact algorithm in
\(O((\tau m+1)L^2+\binom{m}{k}(\tau k+1)L^2)\)
bit operations.

There is also an exact algorithm exponential only in the listed support size. For each \(\sigma\in\{1,2\}^{T}\), define
\(G_\sigma(S)=\sum_t\mu_t b_{t,\sigma(t)}(S)\).
Positivity of the masses and independent choice of each type’s layer give
\(F(S)=\max_\sigma G_\sigma(S)\).
Both optimization domains are finite, so
\(\max_{|S|=k}F(S)=\max_\sigma\max_{|S|=k}G_\sigma(S)\).

For fixed \(\sigma\), assign candidate \(c\) weight
\(w_\sigma(c)=\sum_t\mu_t(m-r_{t,\sigma(t)}(c))\).
Since \(G_\sigma(S)=\sum_{c\in S}w_\sigma(c)\), selecting the \(k\) largest weights maximizes it. Using common-denominator integer weights yields the safe bit-operation bound
\(O(2^\tau(\tau m+m\log(m+1)+k+1)L^2)\).

Thus fixed support size is polynomial-time solvable, while unrestricted support gives an \(\mathrm{NP}\)-complete problem. In particular, \(k=1\) is polynomial by checking every candidate, and \(k=m\) requires evaluating only the unique committee.

⟨structured verdict parsed — rendered above⟩

The prover’s argument resolves the task: the normalized rational-mass decision problem is \(\mathrm{NP}\)-complete, including the restriction to dyadic masses. I found no mathematical errors or gaps requiring repair. The additional parameterized-hardness and algorithmic claims are also justified.

1. The cited source theorem applies

The source states that Max-\(k\)-Borda is \(\mathrm{NP}\)-hard and \(\mathrm{W}[1]\)-hard with respect to \(k\), even with two layers. Its definitions use strict complete rankings, candidate scores \(m-r(c)\), and a voter’s maximum committee score over layers, summed across voters. Its decision version asks for a size-\(k\) committee meeting a threshold. These match the source problem stated by the prover. [Definition 1 and Theorem 1](https://ecai2020.eu/papers/846_paper.pdf)

The restriction to a nonempty source electorate causes no difficulty: instances with no voters have constant score and are trivially decidable.

2. Padding and normalization are correct

Every step in the reduction checks out:

• Duplicating each original voter doubles its contribution, so the original electorate contributes \(2H(S)\).
• The smallest power of two \(N\) satisfying \(N\ge 2n\) is even. Therefore \(p=(N-2n)/2\) is a nonnegative integer.
• For a ranking and its reverse, the positions sum to \(m+1\). Their Borda scores consequently sum to \(m-1\) for each candidate.
• Each padding voter has identical layers, so taking its maximum does not change its ordinary committee score. Each padding pair therefore contributes exactly \(k(m-1)\).
• The padded electorate has exactly \(2n+2p=N\) voters and total score \(2H(S)+pk(m-1)\).

Grouping ordered ranking pairs preserves the total contribution of every committee. Every retained multiplicity \(a_t\) is positive, and their sum is \(N\). Thus \(\mu_t=a_t/N\) gives distinct listed types with positive normalized dyadic masses.

The threshold transformation is exact:
\[ F(S)-q=\frac{2(H(S)-R)}{N}. \]
Since \(N>0\), the claimed equivalence holds in both directions, including equality. No uniqueness or tie-breaking assumption is used.

This calculation remains valid when \(p=0\), when padding types coincide with original types, and when the two padding rankings coincide because \(m=1\).

3. The reduction has polynomial size

Minimality of \(N\) gives \(N<4n\). Duplication introduces no new ranking types, and padding introduces at most two, so \(\tau\le n+2\).

The multiplicities and denominator require \(O(\log(n+1))\) bits. The transformed threshold has polynomial encoding length: its numerator combines the source threshold with a product of explicitly bounded integer parameters.

Constructing fewer than \(4n\) voters and grouping their explicitly represented rankings takes polynomial time in the source input length. The reduction preserves \(k\), so it also provides the required parameterized reduction for the stated \(\mathrm{W}[1]\)-hardness conclusion.

4. Membership in \(\mathrm{NP}\) is established

A list of \(k\) candidates is a polynomial-size certificate. Checking membership and distinctness verifies that it represents an admissible committee.

For every type, the computed score is an integer satisfying
\[ 0\le u_t\le k(m-1). \]

The common denominator \(D=d_q\prod_t d_t\) is positive and divisible by every denominator appearing in the comparison. Multiplication by \(D\) therefore preserves the threshold inequality exactly, including when \(q\) is negative.

The arithmetic-size claims are sound:

• The bit length of \(D\) is \(O(L)\).
• Positivity and normalization imply \(a_t/d_t\le 1\). Hence each score term, and the complete score numerator, is bounded by \(Dk(m-1)\).
• The threshold-side integer \(h(D/d_q)\) has \(O(L)\) bits, using the encoded length of \(h\) and the bound on \(D\).
• The explicitly listed rankings ensure that the additional bit lengths arising from \(m\) and \(k\) are covered by \(O(L)\).

With elementary integer arithmetic, the stated verification bound
\[ O((\tau m+\tau k+1)L^2) \]
is a valid conservative bound. Thus the membership argument is rigorous.

5. The supplementary running-time claims are correct

Committee enumeration examines exactly \(\binom{m}{k}\) committees. The stated preprocessing and per-committee costs support the claimed bound.

For the support-based algorithm, positivity of the masses permits each type’s maximizing layer to be chosen independently. Consequently,
\[ F(S)=\max_{\sigma\in\{1,2\}^{T}}G_\sigma(S). \]
Both domains are finite, so exchanging their maximizations is valid.

For fixed \(\sigma\), the objective is the sum of individual candidate weights. Selecting the \(k\) largest weights therefore maximizes it; ties may be resolved arbitrarily. Computing common-denominator integer weights and sorting supports the stated bound
\[ O(2^\tau(\tau m+m\log(m+1)+k+1)L^2). \]

The conclusions for fixed \(\tau\), for \(k=1\), and for \(k=m\) follow. Polynomial solvability at fixed support size is a parameter restriction, not an encoding-dependent complexity split.

No additional clarification is needed to make the proof verifiable.

⟨structured verdict parsed — rendered above⟩