Answer: \(\mathrm{NP}\text{-hard}\) for every fixed positive \(k\).
Proposition 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe winner determination problem for binomial-k rules F{k} is ΘP 2 -complete for k ∈O(1).
statement extracted from the paper’s text layer; consult the paper for the exact wording
For a fixed constant {k}, an instance gives an integrity constraint Γ, a support of τ feasible ballots {t} with positive rational masses μₜ summing to 1, and a partial ballot b on a set of issues J. For each feasible consensus ballot x, let Sₖ,μ(x) = Σₜ μₜ ⋅ {Agr(t,x) choose {k}}. Does there exist a score-maximizing feasible x that agrees with b on every issue in J?
Fix a positive integer constant \(k\); instances have \(m\ge k\) binary issues and an explicitly encoded propositional formula \(\Gamma\) over their variables. A feasible ballot is \(x\in\{0,1\}^{m}\) satisfying \(\Gamma\).
A society is given by its support: a list \(T\) of \(\tau\ge1\) distinct feasible ballot types, each with positive mass \(\mu_t\) encoded as a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length, including \(\Gamma\) and the masses; state running times in \(m,\tau,L\), with \(k\) fixed.
The input also includes \(J\subseteq\{1,\ldots,m\}\) and a partial ballot \(b:J\to\{0,1\}\), without a promise of feasible extension.
Define \(\operatorname{Agr}(t,x)=|\{j:t_j=x_j\}|\) and \(S_{k,\mu}(x)=\sum_{t\in T}\mu_t\binom{\operatorname{Agr}(t,x)}{k}\), using \(\binom{a}{k}=0\) when \(a<k\). Winners are all feasible ballots attaining the global maximum; ties are retained.
The decision problem asks whether some winner \(x\) satisfies \(x_j=b(j)\) for every \(j\in J\).
For each fixed positive integer \(k\), is this rational-mass winner-extension problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For explicit finite lists of agents, binomial winner-extension is stated to be \(\Theta_2^P\)-complete for every fixed positive \(k\). [Source](https://cdn.aaai.org/ojs/10018/10018-13-13546-1-2-20201228.pdf)
No result settling exactly the normalized, binary-rational support formulation was located in the literature search.
For every fixed positive integer \(k\), the rational-mass winner-extension problem is NP-hard under polynomial-time many-one reductions. Thus, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
In fact, hardness holds with \(\tau=3\), all masses equal to \(1/3\), and a partial ballot fixing just one issue. The construction below guarantees that this partial ballot has a feasible extension, so the reduction concerns optimality as well as feasibility.
Let \(\varphi(u_1,\ldots,u_n)\) be a propositional formula whose satisfiability we wish to decide. We may assume \(n\geq1\), adding an unused variable if necessary. Fix \(k\), and put
\(N=n+1,\qquad d=6N,\qquad p=32kd,\qquad m=p+3d+2N.\)
The issues consist of:
Define three support types \(t_1,t_2,t_3\). In \(t_r\), all padding issues are zero, block \(B_r\) is entirely one, and the other two blocks are entirely zero. Every assignment pair is \((0,0)\), and \((q,q')=(1,1)\).
These types are distinct. Give each mass \(1/3\).
We also define candidate ballots by the following conditions:
These conditions have an explicitly encoded propositional formula. More precisely, let \(H_r\) be the conjunction of literals specifying the entire ballot \(t_r\), and let \(Z\) require every padding and block issue to be zero. Set
\(\Gamma=(H_1\lor H_2\lor H_3)\lor\left[Z\land\bigwedge_{i=1}^{n}(v_i\leftrightarrow\neg u_i)\land(q'\leftrightarrow\neg q)\land(\neg q\lor\varphi)\right].\)
Consequently, the feasible ballots are exactly the three support types and the candidate ballots. All listed support types are feasible, as required. Candidate ballots always exist: choose \(q=0\) and any assignment to the \(u_i\).
The partial ballot fixes only \(q=1\). Each support type extends it, so feasible extension is guaranteed.
Every candidate ballot disagrees with each support type on exactly \(d+N\) issues:
Thus every candidate has the same score
\(C=\binom{m-d-N}{k}.\)
Two different support types disagree on exactly \(2d\) issues. Therefore each support type has score
\(V=\dfrac{1}{3}\left[\binom{m}{k}+2\binom{m-2d}{k}\right].\)
We now prove \(C>V\) for every positive \(k\).
Write \(F(a)=\binom{a}{k}\), and define
\(H=\binom{m-1}{k-1},\qquad G=\binom{m-2d}{k-1}.\)
Our parameter choices ensure \(m-2d\geq k-1\), so these quantities are positive. We first establish
\(G>\dfrac{7}{8}H.\)
For \(k=1\), both quantities equal one. For \(k\geq2\),
\(\displaystyle \frac{G}{H}=\prod_{i=0}^{k-2}\frac{m-2d-i}{m-1-i}=\prod_{i=0}^{k-2}\left(1-\frac{2d-1}{m-1-i}\right).\)
All subtracted fractions lie in \([0,1]\). The elementary inequality \(\prod_i(1-a_i)\geq1-\sum_i a_i\) for such fractions follows by induction from \((1-a)(1-b)\geq1-a-b\). Hence
\(\displaystyle \frac{G}{H}\geq1-\frac{(k-1)(2d-1)}{m-k+1}.\)
Since \(m=p+3d+2N\), \(p=32kd\), and \(d\geq1\), we have \(m-k+1\geq16kd\). It follows that
\(\displaystyle \frac{G}{H}\geq1-\frac{k-1}{8k}>\frac{7}{8}.\)
Next, Pascal’s identity gives, for the values of \(a\) used below,
\(\displaystyle F(m)-F(m-a)=\sum_{h=1}^{a}\binom{m-h}{k-1}.\)
Because the summands are nonincreasing in \(h\),
\(F(m)-F(m-d-N)\leq(d+N)H=7NH,\)
whereas
\(F(m)-F(m-2d)\geq2dG=12NG.\)
Consequently,
\(\displaystyle F(m)-V=\frac{2}{3}\bigl(F(m)-F(m-2d)\bigr)\geq8NG>7NH\geq F(m)-C.\)
Subtracting from \(F(m)\) proves \(C>V\).
Thus the winners are exactly all candidate ballots.
A winning ballot extends the partial ballot \(q=1\) precisely when there is a candidate with \(q=1\). By the definition of candidates, this occurs precisely when \(\varphi\) is satisfiable.
This proves the required equivalence:
\(\varphi\text{ is satisfiable}\quad\Longleftrightarrow\quad\text{some winner extends the specified partial ballot}.\)
For fixed \(k\), the construction has \(m=O_k(n+1)\) and \(\tau=3\). The masses have constant encoding length. Using binary issue indices, the total output length is
\(L=O_k\bigl(|\varphi|+(n+1)\log(n+2)\bigr).\)
The construction can be produced in time polynomial in the source input length. It is therefore a polynomial-time many-one reduction, establishing NP-hardness for every fixed positive \(k\).
There is also an immediate transfer from the finite-agent formulation. Given an explicit profile of \(a\geq1\) agents, merge identical ballots. If type \(t\) occurs \(c_t\) times, assign mass \(\mu_t=c_t/a\). Then, for every feasible \(x\),
\(\displaystyle S_{k,\mu}(x)=\frac{1}{a}\sum_{i=1}^{a}\binom{\operatorname{Agr}(t_i,x)}{k}.\)
This positive scaling preserves every winner, including all ties. The resulting support and binary-rational masses have polynomial encoding length. Therefore the finite-profile hardness stated in [Proposition 3 of the cited paper](https://cdn.aaai.org/ojs/10018/10018-13-13546-1-2-20201228.pdf) transfers directly. The reduction above independently proves the NP-hardness needed here.
For completeness, exact rational arithmetic gives an upper bound of \(\mathrm{P}^{\mathrm{NP}}\). Write each mass as \(a_t/d_t\), and set
\(\displaystyle D=\prod_{t\in T}d_t,\qquad W_t=a_t(D/d_t),\qquad Q(x)=\sum_{t\in T}W_t\binom{\operatorname{Agr}(t,x)}{k}.\)
Then \(Q(x)=D S_{k,\mu}(x)\), all \(W_t\) are positive integers, and \(\sum_tW_t=D\). Thus
\(0\leq Q(x)\leq D\binom{m}{k}.\)
The relevant integers have bit length \(B=O(L+k\log(m+1))\). With ordinary integer arithmetic, feasibility and \(Q(x)\) can be checked in time
\(O_k\bigl((L+m\tau)B^2\bigr).\)
An \(\mathrm{NP}\) oracle can decide whether a feasible ballot has \(Q(x)\geq z\). Binary search finds the maximum using \(O(B)\) oracle queries; one additional query tests whether a ballot attaining that maximum extends \(b\). This establishes the upper bound without expanding rational masses into agents.
The requested polynomial-time-versus-NP-hard question is therefore settled for every fixed positive \(k\).
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and rigorous. It establishes NP-hardness for every fixed positive integer \(k\), even with three distinct support types, equal masses, and a partial ballot fixing one issue that has a feasible extension.
No major or minor mathematical issues were found. The additional \(\mathrm{P}^{\mathrm{NP}}\) upper bound is also justified.
The reduction fixes \(k\) and starts with a satisfiability instance \(\varphi\) on \(n\geq1\) variables. Adding an unused variable preserves satisfiability.
The definitions
\[
N=n+1,\qquad d=6N,\qquad p=32kd,\qquad m=p+3d+2N
\]
give positive integer block sizes and ensure \(m\geq k\). There are exactly \(m\) issues: the padding issues, three blocks, and \(N\) pairs.
The support types are distinct because their all-one blocks occupy different positions. Their masses are positive binary rationals and sum to one. Each support type satisfies its corresponding disjunct \(H_r\), so all listed types are feasible.
Assessment: Valid instance construction; all promises in the task are satisfied.
Each \(H_r\) specifies precisely one complete ballot. The other disjunct of \(\Gamma\) imposes exactly the stated candidate conditions:
Thus the feasible set consists exactly of the three support types and the candidate ballots. These classes are disjoint because every support type has a nonzero block, whereas every candidate has all blocks zero.
Candidates exist regardless of satisfiability: setting \(q=0\) makes the last condition true for every assignment to the \(u_i\).
Every support type has \(q=1\), so the prescribed partial ballot always has a feasible extension.
Assessment: The feasible-set characterization and the nonvacuity claim are correct.
For each candidate and each support type, the disagreements are exactly:
The disagreement count is therefore \(d+N\). Every candidate has agreement \(m-d-N\) with every support type, giving
\[
C=\binom{m-d-N}{k}.
\]
Two distinct support types disagree exactly on their two distinguished blocks, hence on \(2d\) coordinates. A support type agrees with itself on all coordinates. Therefore
\[
V=\frac13\left[\binom{m}{k}+2\binom{m-2d}{k}\right].
\]
The normalization by equal masses is handled correctly in both calculations.
Assessment: Both exact score formulas are correct.
The parameters ensure that \(m-2d\geq k-1\), so
\[
H=\binom{m-1}{k-1},\qquad G=\binom{m-2d}{k-1}
\]
are positive.
For \(k=1\), both equal one, and the claimed strict inequality \(G>\frac78H\) holds.
For \(k\geq2\), the factorial cancellation in
\[
\frac GH
=\prod_{i=0}^{k-2}
\left(1-\frac{2d-1}{m-1-i}\right)
\]
is correct. All factors have the stated domain: the denominators are positive, and the subtracted fractions lie in \([0,1]\).
The product inequality used by the prover is stated and justified. The smallest denominator is \(m-k+1\), so it yields
\[
\frac GH\geq
1-\frac{(k-1)(2d-1)}{m-k+1}.
\]
The parameter bound \(m-k+1\geq16kd\) is valid. Consequently, the subsequent estimate
\[
\frac GH\geq1-\frac{k-1}{8k}>\frac78
\]
holds for every positive integer \(k\).
Assessment: The ratio estimate, including the separate \(k=1\) case, is sound.
Pascal’s identity gives the stated telescoping formula
\[
F(m)-F(m-a)=
\sum_{h=1}^{a}\binom{m-h}{k-1}.
\]
Both values used for \(a\) are positive integers within the valid range. The binomial summands are nonincreasing as \(h\) increases; for \(k=1\), they are constant.
Since \(d+N=7N\), the candidate deficit satisfies
\[
F(m)-C\leq7NH.
\]
Since \(2d=12N\), the support deficit satisfies
\[
F(m)-V
=\frac23\bigl(F(m)-F(m-2d)\bigr)
\geq8NG.
\]
The strict ratio bound gives \(8NG>7NH\). Thus the complete inequality chain
\[
F(m)-V>F(m)-C
\]
is valid and has the correct direction. It proves \(C>V\).
Because candidates exist and the feasible set has already been characterized completely, the winners are exactly all candidate ballots. No additional feasible ballot class or tie case is omitted.
Assessment: The central strict score gap is proved.
A winner extending \(q=1\) must be a candidate. Such a candidate exists precisely when its assignment satisfies \(\varphi\). Conversely, a satisfying assignment yields a candidate with \(q=1\), and every candidate is a winner.
The equivalence therefore holds in both directions, including unsatisfiable instances. In that case, feasible extensions with \(q=1\) still exist among the support types, but the strict score gap excludes them from the winners.
Assessment: The reduction addresses winner optimality and establishes the required many-one equivalence.
For fixed \(k\), the number of constructed issues is \(O_k(n+1)\). The support size is exactly three, and the masses have constant encoding length.
The formula contains three complete ballot descriptions, the zero-coordinate constraints, the pair constraints, and one copy of \(\varphi\). With binary issue indices, the claimed bound
\[
L=O_k\bigl(|\varphi|+(n+1)\log(n+2)\bigr)
\]
is valid under the usual explicit propositional encoding.
The construction is polynomial in the source input length. It does not enumerate satisfying assignments or candidate ballots.
Assessment: The reduction meets the required encoding and polynomial-time conditions.
Merging equal ballots and assigning mass \(c_t/a\) produces distinct feasible support types with positive rational masses summing to one. The score identity in the output is exact, and multiplication by the positive constant \(1/a\) preserves the entire winner set, including ties.
The support encoding is polynomial in the explicit profile length. The cited paper’s Proposition 3 concerns fixed-\(k\) binomial winner determination, and its definition of winner determination matches the partial-ballot extension question here. [Cited paper, Section 2.4](https://cdn.aaai.org/ojs/10018/10018-13-13546-1-2-20201228.pdf)
Assessment: The transfer is valid. The independent reduction already establishes the requested NP-hardness.
Taking \(D\) to be the product of the positive denominators makes each \(W_t=a_t(D/d_t)\) a positive integer. Normalization gives
\[
\sum_tW_t=D,
\]
and hence the claimed integer score bound
\[
0\leq Q(x)\leq D\binom{m}{k}
\]
is correct.
The product denominator has bit length bounded by the sum of the input denominator lengths. For fixed \(k\), the binomial coefficient contributes only \(O_k(\log(m+1))\) further bits. Thus the stated bound on \(B\) is valid.
The proposed verification time is a valid conservative bound using ordinary integer arithmetic. A guessed ballot permits polynomial-time verification of feasibility and the score threshold, so the threshold question is in \(\mathrm{NP}\).
The threshold predicate is monotone. Binary search over the stated integer range takes \(O(B)\) oracle queries. A final query can impose both the partial ballot and the maximum score. The feasible set is nonempty because the support is nonempty and feasible.
Assessment: The \(\mathrm{P}^{\mathrm{NP}}\) upper bound is justified without expanding the rational masses.
There are no identified issues requiring repair. The prover resolves the requested polynomial-time-versus-NP-hard question for every fixed positive \(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.