Answer: Polynomial-time solvable; the problem belongs to \(\mathrm{P}\).
Proposition 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDeciding if x∗is a possible winner for 4- approval with respect to the addition of three new candi- dates, is an NP-complete problem.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an initial candidate set \(X\), three new candidates \(Y\), a target \(x^\star\in X\), and a rational distribution \(\mu\) over rankings of \(X\), is there a completion plan \(q_{t,\pi}\ge 0\) such that \(\sum_{\pi:\,\pi|_X=t}q_{t,\pi}=1\) for each type \(t\), and \(x^\star\) is a \(4\)-approval winner under the resulting mass \(\bar\mu_\pi=\sum_t\mu_tq_{t,\pi}\), with favorable tie-breaking?
Let \(X\) be the initial candidate set, with \(m=|X|\ge 5\), let \(Y\) be a disjoint set of exactly three new candidates, and let \(x^\star\in X\).
A society is given by its support: a list \(T\) of \(\tau\) strict rankings of \(X\), 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 each \(t\in T\), let \(E(t)\) consist of all strict rankings \(\pi\) of \(X\cup Y\) whose restriction to \(X\) is \(t\); the new candidates may be inserted anywhere and in any order.
A completion plan consists of real numbers \(q_{t,\pi}\ge 0\) for \(\pi\in E(t)\), satisfying \(\sum_{\pi\in E(t)}q_{t,\pi}=1\). It induces mass \(\bar\mu_\pi=\sum_{t:\pi\in E(t)}\mu_tq_{t,\pi}\).
Apply \(4\)-approval to the completed society, with scores weighted by \(\bar\mu\). Favorable tie-breaking means that \(x^\star\) wins whenever its score is at least that of every candidate in \(X\cup Y\).
Is deciding whether such a winning completion plan exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite lists of indivisible voters, this problem with \(4\)-approval and exactly three new candidates is NP-complete. [Discrete result](https://ojs.aaai.org/index.php/AAAI/article/download/7640/7501)
The discrete hardness extends to every fixed approval threshold \(K\ge 3\) and number of new candidates \(k\ge 3\). [Later result](https://www.lamsade.dauphine.fr/~lang/papers/clmmx-mss12.pdf)
No result settling this exact divisible-mass completion problem was located in the literature search.
Theorem. The stated decision problem belongs to \(\mathrm{P}\). A winning completion exists exactly when a rational linear program with \(4\tau\) variables is feasible.
Write each original ranking as \(t=(x_{t,1},\ldots,x_{t,m})\), and let \(r_t(x)\) denote the position of \(x\) in \(t\).
Consider an extension of \(t\), and let \(j\) be the number of new candidates among its first four positions. Since there are exactly three new candidates, \(j\in\{0,1,2,3\}\). Exactly \(4-j\) old candidates are approved.
These old candidates must be the first \(4-j\) candidates of \(t\). Indeed, if an old candidate is approved, every old candidate preceding it in \(t\) precedes it in the extension and is also approved.
Conversely, for every \(j\in\{0,1,2,3\}\) and every subset \(S\subseteq Y\) with \(|S|=j\), the approval set
\(\displaystyle S\cup\{x_{t,1},\ldots,x_{t,4-j}\}\)
is attainable. To realize it, rank the members of \(S\) first, then all members of \(X\) in order \(t\), then the members of \(Y\setminus S\). This ranking restricts to \(t\), and its first four positions have exactly the specified candidates. The assumption \(m\ge5\) ensures all required old prefixes exist.
Thus, for old candidates, only the value of \(j\) matters.
For each \(t\in T\) and \(j\in\{0,1,2,3\}\), introduce a variable \(z_{t,j}\). It represents the actual society mass assigned to extensions of \(t\) that approve exactly \(j\) new candidates.
Require
\(\displaystyle z_{t,j}\ge0,\qquad \sum_{j=0}^{3}z_{t,j}=\mu_t\quad(t\in T).\)
For each \(x\in X\), define the linear expression
\(\displaystyle s_x(z)=\sum_{t\in T}\sum_{j=0}^{3}z_{t,j}\,\mathbf{1}\{r_t(x)\le4-j\}.\)
By the preceding section, this is precisely the score of \(x\) for any completion with these aggregate masses.
Define also
\(\displaystyle h(z)=\sum_{t\in T}\sum_{j=0}^{3}jz_{t,j}.\)
This is the sum of the scores of the three new candidates: mass \(z_{t,j}\) contributes approval to exactly \(j\) of them.
The remaining constraints are
\(\displaystyle s_x(z)\le s_{x^\star}(z)\quad(x\in X\setminus\{x^\star\}),\)
and
\(\displaystyle h(z)\le3s_{x^\star}(z).\)
We prove that this system is feasible exactly when a winning completion exists.
Suppose a winning completion plan \(q\) exists. For an extension \(\pi\), let \(j(\pi)\) count its approved new candidates. Set
\(\displaystyle z_{t,j}=\mu_t\sum_{\substack{\pi\in E(t)\\j(\pi)=j}}q_{t,\pi}.\)
These variables are nonnegative. Since the four possible values of \(j(\pi)\) partition \(E(t)\), their sum for each \(t\) is \(\mu_t\).
Section 1 shows that every old candidate \(x\) has score \(s_x(z)\). Therefore, because \(x^\star\) wins, every old-candidate inequality holds.
Let \(s_y\) be the score of a new candidate \(y\in Y\). Counting approvals to new candidates gives
\(\displaystyle h(z)=\sum_{y\in Y}s_y.\)
Winning implies \(s_y\le s_{x^\star}(z)\) for each of the three new candidates. Summing these inequalities yields \(h(z)\le3s_{x^\star}(z)\). Hence the linear system is feasible.
Suppose the linear system has a feasible solution \(z\). Fix an ordering of \(Y\).
For every \(t\), every \(j\), and every subset \(S\subseteq Y\) of size \(j\), let \(\pi_{t,S}\) be the canonical extension constructed in Section 1: first \(S\) in the fixed order, then \(X\) in order \(t\), then \(Y\setminus S\) in the fixed order.
Define
\(\displaystyle q_{t,\pi_{t,S}}=\frac{z_{t,j}}{\mu_t\binom{3}{j}}\quad\text{when }|S|=j,\)
and assign probability zero to all other extensions. For fixed \(t\), distinct subsets give distinct approval sets and hence distinct canonical extensions, so this assignment is well defined. Since \(\mu_t>0\),
\(\displaystyle \sum_{\pi\in E(t)}q_{t,\pi} =\sum_{j=0}^{3}\binom{3}{j}\frac{z_{t,j}}{\mu_t\binom{3}{j}} =\frac{\sum_{j=0}^{3}z_{t,j}}{\mu_t}=1.\)
Thus this is an admissible completion plan.
Its old-candidate scores are \(s_x(z)\). To compute a new candidate’s score, observe that a uniformly chosen subset of \(Y\) of size \(j\) contains any fixed \(y\in Y\) with probability \(j/3\). For \(j=0\) this is zero; for \(j\in\{1,2,3\}\), it follows from
\(\displaystyle \frac{\binom{2}{j-1}}{\binom{3}{j}}=\frac{j}{3}.\)
Consequently, each new candidate has score
\(\displaystyle s_y=\sum_{t\in T}\sum_{j=0}^{3}\frac{j}{3}z_{t,j}=\frac{h(z)}{3}\le s_{x^\star}(z).\)
The old-candidate inequalities likewise ensure that every old competitor’s score is at most that of \(x^\star\). Favorable tie-breaking therefore makes \(x^\star\) a winner. This proves sufficiency.
The system has \(4\tau\) variables, \(\tau\) mass equalities, \(m-1\) old-candidate inequalities, one new-candidate inequality, and \(4\tau\) nonnegativity constraints.
After moving terms to the left, every coefficient is an integer of absolute value at most three. The only nonzero right-hand sides are the input rationals \(\mu_t\). Computing the ranks \(r_t(x)\) takes time polynomial in \(m,\tau,L\), and a dense encoding of the system has length \(O(m\tau+\tau^2+L)\).
We use the standard polynomial-time theorem for rational linear programming: feasibility of finitely many non-strict linear inequalities with rational coefficients can be decided in time polynomial in their total binary encoding length. Equalities can be replaced by two inequalities, so the theorem applies directly here. It decides exact feasibility over the reals, including boundary cases where candidates tie.
By Sections 3 and 4, this feasibility decision answers the original question exactly.
The [cited discrete result, Proposition 3](https://ojs.aaai.org/index.php/AAAI/article/download/7640/7501), concerns indivisible voters. Our reconstruction splits each support mass among several extensions, which the present problem explicitly permits. An indivisible voter cannot generally realize that split. Thus the discrete hardness result does not obstruct this polynomial-time algorithm for divisible mass.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The approval-set characterization is exact, the linear program is equivalent to the existence of a winning completion, and its encoding has polynomial length. No major or minor mathematical issues were found.
Verified. Every extension has exactly \(j\in\{0,1,2,3\}\) new candidates among its first four positions, leaving exactly \(4-j\) approved old candidates.
Preserving the original strict ranking forces those old candidates to form its prefix of length \(4-j\): an approved old candidate cannot have an unapproved old predecessor.
The converse construction is valid for every permitted \(j\) and every subset \(S\subseteq Y\) of size \(j\). Placing \(S\) first, followed by the entire original ranking and then the remaining new candidates, produces precisely the claimed approval set. The assumption \(m\ge5\) guarantees every required prefix exists.
Thus aggregating extensions by \(j\) preserves all old-candidate scores exactly.
Verified. The variables \(z_{t,j}\) represent society mass, rather than conditional probabilities. Accordingly, the normalization \(\sum_{j=0}^{3}z_{t,j}=\mu_t\) is correct.
The expression \(s_x(z)\) counts precisely the mass approving each old candidate. The expression \(h(z)\) counts total approvals received by the three new candidates.
The old-candidate inequalities express the required comparisons with \(x^\star\). The inequality \(h(z)\le3s_{x^\star}(z)\) is necessary; its sufficiency requires the reconstruction in Section 4 and is established there.
Verified. Aggregating a completion plan by its number of approved new candidates gives nonnegative variables with the stated mass equalities.
The approval-set characterization proves that aggregation preserves every old-candidate score. Summing the three new-candidate winning inequalities gives exactly the stated inequality for \(h(z)\).
There is no loss of a necessary condition in this direction.
Verified. The canonical extensions are admissible strict rankings. For fixed \(t\), distinct subsets yield distinct approval sets, so the probability assignment is unambiguous.
Every assigned probability is nonnegative, and division by \(\mu_t\) is legitimate because the task assumes positive masses. The displayed normalization calculation correctly gives total conditional probability one.
The new-candidate inclusion calculation is also correct:
Consequently, the reconstruction gives each new candidate exactly \(h(z)/3\), while preserving the old-candidate scores \(s_x(z)\). All competitors therefore have score at most \(s_{x^\star}(z)\). This establishes sufficiency under the specified favorable tie-breaking.
The reconstruction uses only the permitted division of support mass; it assumes no additional freedom.
Verified. The variable and constraint counts are correct.
For an old-candidate inequality, each coefficient after subtraction belongs to \(\{-1,0,1\}\). For the new-candidate inequality, each coefficient has the form \(j-3\mathbf{1}\{r_t(x^\star)\le4-j\}\), whose absolute value is at most three. Mass equalities and nonnegativity constraints also satisfy the claimed coefficient bound.
The dense encoding bound \(O(m\tau+\tau^2+L)\) is valid: the matrix has polynomially many constant-size coefficients, and the rational right-hand sides are input masses.
The invoked rational linear-programming theorem is stated precisely enough for this application. Its hypotheses hold: the system is finite, all coefficients and right-hand sides are rational, and every constraint is non-strict. Replacing equalities with two inequalities preserves feasibility and polynomial encoding length. Exact feasibility over the reals includes tied-score boundary cases.
No assumption about a positive feasibility margin or integral solutions is needed.
Verified. The cited paper defines profiles using a finite list of voters, assumes favorable tie-breaking, and states the claimed discrete hardness in Proposition 3. [Original paper](https://ojs.aaai.org/index.php/AAAI/article/download/7640/7501)
The prover correctly distinguishes that model from the present mass-splitting model. The discrete result is contextual and is not used to justify the polynomial-time conclusion.
None. No additional clarification or missing lemma is needed to verify the argument.
⟨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.