Answer: Egalitarian-SNTV is in \(\mathrm{P}\), with running time \(O(L+m+\tau)\) on a standard word RAM. Egalitarian-Bloc and egalitarian-\(k\)-Borda are \(\mathrm{NP}\)-complete, even with uniform support masses. Each rule admits an exact algorithm using \(O(L^2+m\tau+\binom{m}{k}\tau k)\) word operations.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateEgalitarian-SNTV is in P, but the problem of deciding if there exists a committee with at least a given score is NP-hard both for egalitarian-Bloc and egalitarian-k-Borda.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) candidates, committee size \(k\), a rational distribution \(\mu\) over a support \(T\) of complete rankings, a fixed rule \(r\in\{\text{egalitarian-SNTV},\text{egalitarian-Bloc},\text{egalitarian-}k\text{-Borda}\}\), and a threshold \(q\), decide whether there is a committee \(W\subseteq C\) with \(|W|=k\) such that \(\min_{t\in T} f^r_{m,k}(\operatorname{pos}_t(W))\ge q\); determine the complexity in \(m\), \(|T|\), and the input bit length.
Let \(C\) contain \(m\ge 1\) candidates, let \(1\le k\le m\), and let \(q\in\mathbb{Q}\) be a binary-encoded threshold.
A society is given by its support: a nonempty list \(T\) of \(\tau\) distinct strict complete rankings, each with 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; \(L\) is the total input bit length.
For \(W\subseteq C\) with \(|W|=k\), define \(s_t^r(W)\) as follows: egalitarian-SNTV uses the number of selected candidates ranked first; egalitarian-Bloc uses the number ranked among the first \(k\); egalitarian-\(k\)-Borda uses the sum of their Borda scores.
For a fixed rule \(r\) among these three, the decision problem asks whether some such \(W\) satisfies \(\min_{t\in T}s_t^r(W)\ge q\). Scores are unweighted by mass, and threshold equality is accepted.
For each fixed rule \(r\), is this decision problem in \(\mathrm{P}\) or NP-hard, with running times expressed in \(m,\tau,k,L\)?
For finite voter lists, egalitarian-SNTV is in \(\mathrm{P}\), while the threshold problems for egalitarian-Bloc and egalitarian-\(k\)-Borda are NP-hard; egalitarian scores are also invariant under voter duplication. [Verified source](https://www.ijcai.org/proceedings/2018/0008.pdf).
The support formulation therefore inherits these classifications; this is an inference from the definitions and verified results, so the stated target is already settled.
For each fixed rule, with \(k\) part of the input, the support formulation has the following complexity:
| Rule | Complexity |
|---|---|
| Egalitarian-SNTV | \(\mathrm{P}\) |
| Egalitarian-Bloc | \(\mathrm{NP}\)-complete |
| Egalitarian-\(k\)-Borda | \(\mathrm{NP}\)-complete |
The hardness statements already hold when all support masses equal \(1/\tau\). Below, we prove the transfer from finite voter lists and give explicit algorithmic bounds.
Write \(\operatorname{pos}_t(c)\) for the position of candidate \(c\) in ranking \(t\), with the first position numbered \(1\). The three scores are
Every score is a nonnegative integer. Consequently, putting \(Q=\lceil q\rceil\), the acceptance condition is exactly
\(s_t(W)\ge Q\quad\text{for every }t\in T.\)
This equivalence includes threshold equality. Computing \(Q\) from the binary-rational encoding takes \(O(L^2)\) bit operations using ordinary integer division.
The masses never occur in these inequalities. Their positivity ensures that every listed ranking belongs to the support; their magnitudes have no further effect.
Let \(F=\{c\in C:c\text{ is ranked first in some }t\in T\}\), and put \(d=|F|\).
For every committee \(W\) and ranking \(t\), its SNTV score belongs to \(\{0,1\}\). Moreover,
\(\min_{t\in T}s_t(W)=1\quad\Longleftrightarrow\quad F\subseteq W.\)
Indeed, a ranking gives score \(1\) precisely when its unique first-ranked candidate is selected. Requiring this for every ranking requires exactly the inclusion \(F\subseteq W\).
A size-\(k\) committee containing \(F\) exists precisely when \(d\le k\): necessity follows from cardinality, and sufficiency follows by adding \(k-d\) candidates from \(C\setminus F\), since \(k\le m\).
Thus the decision algorithm is:
On a standard word RAM with candidate identifiers indexed by \(1,\ldots,m\), reading the input, comparing \(q\) with \(0,1\), and marking the first-ranked candidates takes \(O(L+m+\tau)\) time. This proves membership in \(\mathrm{P}\), including rational thresholds.
The external result we use is Theorem 1 of Aziz, Faliszewski, Grofman, Slinko, and Talmon: for finite lists of strict complete rankings, deciding whether a size-\(k\) committee has egalitarian score at least a given threshold is NP-hard for both Bloc and \(k\)-Borda. Their scoring definitions agree with those above, including Borda score \(m-\operatorname{pos}_t(c)\). [Egalitarian Committee Scoring Rules, Sections 2–3 and Theorem 1](https://www.ijcai.org/proceedings/2018/0008.pdf).
Fix either of these two rules. Given a finite-list instance with nonempty voter list \(V\), construct a support instance as follows:
This produces a valid society: the rankings are distinct, every mass is a positive binary rational, and the masses sum to \(1\).
For every committee \(W\),
\(\min_{v\in V}s_v(W)=\min_{t\in T}s_t(W).\)
To justify this equality, every ranking appearing in \(V\) appears in \(T\), and each ranking in \(T\) appears in \(V\). Repetition therefore changes neither the set of score values nor its minimum. Hence the original instance and the constructed instance have identical answers.
The construction is polynomial in the original input length. Rankings can be sorted and deduplicated in polynomial time; there are at most \(|V|\) remaining rankings; and each mass \(1/|T|\) needs \(O(\log(|V|+1))\) bits.
This is a polynomial-time many-one reduction. The cited finite-list hardness theorem therefore proves NP-hardness of both support problems, even with uniform masses.
Conversely, any support instance can be converted into a finite voter list containing each support ranking once, discarding the masses. The same equality proves that this conversion preserves the answer. No expansion of rational masses into voter multiplicities is needed.
A certificate is a list of \(k\) distinct candidates. Its length is polynomial in \(L\). After checking that it defines a valid committee, compute its score for each support ranking and compare every score with \(Q\).
The scores are bounded respectively by \(1\), \(k\), and \(k(m-1)\), so they use \(O(\log(m+1))\) bits because \(k\le m\). All verification steps take polynomial time in \(L\). Thus all three problems belong to \(\mathrm{NP}\); combined with Section 3, this establishes NP-completeness for Bloc and \(k\)-Borda.
For completeness, an explicit exact algorithm for any of the rules enumerates the \(\binom{m}{k}\) committees. Precompute each ranking’s candidate scores in \(O(m\tau)\) word operations. Evaluating one committee then takes \(O(\tau k)\) word operations.
Using words of \(O(\log(m\tau+2))\) bits, a valid total upper bound is
\(O\!\left(L^2+m\tau+\binom{m}{k}\tau k\right)\)
word operations, including threshold preprocessing. A corresponding conservative bit-operation bound is
\(O\!\left(L^2+\left(m\tau+\binom{m}{k}\tau k\right)\log(m\tau+2)\right).\)
In particular, fixed \(k\) gives a polynomial-time algorithm for every rule. The NP-completeness classifications concern unrestricted input \(k\).
⟨structured verdict parsed — rendered above⟩
The classification is correct: egalitarian-SNTV is in \(\mathrm{P}\), and egalitarian-Bloc and egalitarian-\(k\)-Borda are \(\mathrm{NP}\)-complete when \(k\) is part of the input. The support reduction is rigorous and preserves answers exactly.
There is one minor gap in the implementation details supporting the explicit exhaustive-search bounds. It does not affect the complexity classifications.
All three displayed score definitions agree with the task. In particular, a candidate at position \(i\) receives Borda score \(m-i\).
Every committee score is an integer. Therefore, for every ranking and committee,
\[
s_t(W)\ge q \quad\Longleftrightarrow\quad s_t(W)\ge \lceil q\rceil.
\]
This remains valid for negative thresholds and includes equality.
The claimed \(O(L^2)\) bit-operation bound for computing the ceiling is valid using ordinary binary integer division. For negative numerators, the implementation must use mathematical ceiling rather than truncation toward zero; the write-up explicitly specifies ceiling, so there is no mathematical error.
The masses are irrelevant to the stated inequalities. Positivity and the nonempty-support assumption ensure that the minimum ranges over exactly the listed rankings.
Assessment: Correct.
A strict ranking has exactly one first-ranked candidate, so its SNTV score is either \(0\) or \(1\). Consequently,
\[
\min_{t\in T}s_t(W)=1 \quad\Longleftrightarrow\quad F\subseteq W.
\]
The committee-extension argument is valid: if \(d\le k\), then \(k-d\le m-d\), so sufficiently many candidates remain outside \(F\).
The three threshold branches exhaust all rational thresholds:
These arguments also cover \(m=1\) and \(k=m\). With indexed candidate identifiers, the stated \(O(L+m+\tau)\) RAM bound is justified.
Assessment: Correct.
The cited source states precisely the required threshold hardness result in Theorem 1. Its definitions use complete rankings, committees of size \(k\), the minimum voter score, and Borda score \(m-i\). The theorem therefore concerns the same finite-list decision problems used in the reduction. [Aziz et al., Sections 2–3 and Theorem 1](https://www.ijcai.org/proceedings/2018/0008.pdf).
The citation establishes threshold NP-hardness, rather than merely hardness of some different winner-identification problem.
Assessment: The cited theorem applies.
Deduplication preserves the set of ranking-dependent score values for every committee. Hence it preserves their minimum and the answer to the threshold question.
The resulting support is nonempty. Uniform masses \(1/|T|\) are positive rationals, sum to \(1\), and have polynomial-length binary numerator–denominator encodings. “Binary rational” is correctly read here as a binary-encoded rational, consistently with the task.
Sorting and deduplicating explicitly listed rankings takes polynomial time in the source input length. The output has polynomial length, including its masses.
The reverse conversion—listing each support ranking once and discarding masses—also preserves answers and requires no expansion by denominators.
Assessment: Correct polynomial-time many-one reduction; uniform-mass hardness follows.
A committee certificate has polynomial length. Distinctness, membership in \(C\), and cardinality can all be checked in polynomial time.
The score bounds \(1\), \(k\), and \(k(m-1)\) are valid. Since \(k\le m\), each score occupies \(O(\log(m+1))\) bits, including the zero-score case.
Computing scores and comparing them with the binary-encoded threshold is polynomial in \(L\). Thus the NP-membership argument is valid, and combining it with the reduction proves both NP-completeness claims.
Assessment: Correct.
Precomputing candidate scores uses \(O(m\tau)\) operations. Summing the selected candidates’ scores uses \(O(\tau k)\) arithmetic operations per committee. Enumerating the \(\binom{m}{k}\) committees introduces no larger asymptotic overhead.
Minor issue: The stated per-committee bound does not explicitly account for comparing bounded scores with an arbitrarily long \(Q\). Furthermore, words of \(O(\log(m\tau+2))\) bits need not suffice to address preprocessing storage depending on \(L\), because threshold and mass encodings can make \(L\) arbitrarily large independently of \(m\tau\).
Minimum clarification needed: Specify how threshold preprocessing makes subsequent comparisons fit the claimed operation budget, and state the RAM addressing convention for input-length-dependent storage. These are routine implementation details; no new mathematical argument is needed.
The fixed-\(k\) polynomial-time conclusion remains valid because \(\binom{m}{k}\le m^k\).
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.