Answer: The problem is in \(\mathrm{P}\).
Theorem 1 (informal) — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor AV, SAV, seq-Phragm´en, and Phragmms, the minimum exogenous cost of replacing ℓcan- didates can be computed in O(1) time, assuming we use data from executions of the rules. For details, we refer to our full version, where we also dis- cuss the complexity of this problem for seq-PAV and MES.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(k\), approval cap \(q\), replacement target \(\ell\), rational masses \(\mu\) over approval types \(S \subseteq C\), and fixed tie-breaking, let \(W\) be the AV committee. Add fresh candidates \(D\) of size \(\ell\) and nonnegative masses \(y_B\) over approval types \(B \subseteq C \cup D\) with \(|B| \le q\). Minimize the total added mass \(x = \sum_B y_B\) subject to the resulting tie-broken AV committee replacing exactly \(\ell\) members of \(W\) by \(D\).
Let \(C\) contain \(m\) candidates, with integers \(1\leq\ell\leq k\leq m\) and \(1\leq q\leq m+\ell\). Let \(D\) be a specified set of \(\ell\) fresh candidates, disjoint from \(C\), and fix an input total order on \(C\cup D\) for breaking score ties.
A society is given by its support: the list of the \(\tau\) approval types \(S\subseteq C\) with positive mass, each mass \(\mu_S\) a binary rational, with \(|S|\leq q\) and \(\sum_S\mu_S=1\). Here \(\tau\) is the support size, not the number of possible approval sets.
Let \(W\) be the size-\(k\) approval-voting (AV) committee of this society, using the fixed order restricted to \(C\).
An addition assigns nonnegative real masses \(y_B\) to approval types \(B\subseteq C\cup D\) with \(|B|\leq q\), at cost \(x=\sum_B y_B\). Original ballots and masses remain unchanged; added mass is measured relative to the original total mass.
Let \(W_y\) be the resulting size-\(k\) AV committee using the fixed order. Success means \(D\subseteq W_y\) and \(W_y\cap C\subseteq W\), so exactly \(\ell\) original winners are replaced by \(D\).
Given a nonnegative binary-rational budget \(b\), ask whether a successful addition with \(x\leq b\) exists. Let \(L\) be the total input bit length; state running times in \(m,\tau,L,k,q,\ell\).
Is this continuous AV replacement budget-feasibility problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finitely listed weighted voters, AV replacement cost can be evaluated in \(O(1)\) time given the relevant original winner’s approval weight, under unrestricted added ballot length and tie-breaking favoring fresh candidates. [Source](https://arxiv.org/pdf/2312.11408)
That result already permits divisible voting weights, but does not establish the capped, arbitrary-fixed-order problem above; no result settling this exact formulation was located.
The problem is in \(\mathrm{P}\). In fact, its feasibility criterion has a closed form, including the effect of arbitrary fixed tie-breaking.
The cited [Theorem 2](https://arxiv.org/pdf/2312.11408) establishes the unrestricted-ballot formula under tie-breaking favoring fresh candidates. The proof below handles the ballot cap and the specified order directly.
Write \(\pi(c)\) for the position of candidate \(c\) in the fixed order, with smaller positions winning ties. Define each original approval score by
\(a(c)=\sum_{S\ni c}\mu_S\).
Order the original candidates as \(c_1,\ldots,c_m\) by decreasing score, breaking ties by increasing \(\pi\). Thus \(W=\{c_1,\ldots,c_k\}\).
Set
\(r=k-\ell\), \(p=c_{r+1}\), \(t=a(p)\), \(h=\min\{q,\ell\}\), and \(\beta=\ell t/h\).
Theorem. A successful addition of cost at most \(b\) exists exactly when either:
In particular, scores equal to zero cause no exception: feasibility at zero budget is governed by the same tie-order condition.
Consider any successful addition of cost \(x\). For each candidate \(c\), let
\(z(c)=\sum_{B\ni c}y_B\)
be its added approval score. Its resulting score is \(a(c)+z(c)\) for \(c\in C\), and \(z(c)\) for \(c\in D\).
Since every added ballot has mass counted in \(x\), and approves at most \(q\) candidates,
\(z(d)\leq x\) for every \(d\in D\), and
\(\sum_{d\in D}z(d)\leq qx\).
Success selects exactly \(r\) original candidates. Consequently, at least one candidate \(e\in\{c_1,\ldots,c_{r+1}\}\) is excluded.
Candidate \(e\) originally ranks at least as highly as \(p\). Its score cannot decrease under addition. Moreover, every selected candidate must outrank every excluded candidate under the resulting score and tie order. Therefore, every \(d\in D\) must outrank the original score-order position of \(p\). Explicitly,
To verify the strict assertion, suppose instead that \(z(d)=t\) and \(\pi(d)>\pi(p)\). If \(a(e)>t\), then \(e\) outranks \(d\) by score. Otherwise \(a(e)=t\), and the original ordering gives \(\pi(e)\leq\pi(p)<\pi(d)\); hence \(e\) still outranks \(d\). Increasing \(e\)'s score cannot change this conclusion, contradicting its exclusion.
The score requirements imply \(x\geq t\) and \(qx\geq\ell t\). Thus
\(x\geq\max\{t,\ell t/q\}=\beta\).
It remains to characterize feasibility at \(b=\beta\). The lower bound forces \(x=\beta\), and every fresh candidate then has score exactly \(t\):
The strict requirement above therefore rules out any fresh candidate appearing after \(p\). This proves necessity.
We first construct added ballots giving every fresh candidate any prescribed score \(s\geq0\), while giving no additional approvals to original candidates.
Label \(D=\{d_0,\ldots,d_{\ell-1}\}\). For each \(i\in\{0,\ldots,\ell-1\}\), use the ballot
\(B_i=\{d_i,d_{i+1},\ldots,d_{i+h-1}\}\),
where indices are taken modulo \(\ell\), with mass \(s/h\).
Each ballot approves \(h\leq q\) distinct candidates. Each fresh candidate belongs to exactly \(h\) of these indexed ballots, so its score is \(s\). The total cost is \(\ell s/h\). If some ballot types coincide, their masses are combined; this preserves both scores and cost.
Suppose first that \(b=\beta\) and every fresh candidate precedes \(p\). Apply the construction with \(s=t\).
Every fresh candidate outranks \(p\), by tie-breaking. Each candidate in \(T=\{c_1,\ldots,c_r\}\) also outranks \(p\), whereas every original candidate outside \(T\) ranks at or below \(p\). All original scores remain unchanged. Consequently, every member of \(T\cup D\) outranks every candidate outside that set. Since \(|T\cup D|=k\), the resulting committee is exactly \(T\cup D\). Its cost is \(\ell t/h=\beta=b\).
Now suppose that \(b>\beta\). Choose
\(s=(t+hb/\ell)/2\).
The inequality \(b>\ell t/h\) gives \(s>t\), and the construction costs
\(\ell s/h=(\beta+b)/2<b\).
Every fresh candidate now outranks \(p\) strictly by score. The same comparison with \(T\) shows that the committee is exactly \(T\cup D\). This proves sufficiency.
The decision algorithm is:
Score computation requires at most \(\tau\min\{q,m\}\) score updates. Sorting requires \(O(m\log m)\) comparisons, and checking the fresh candidates requires \(O(\ell)\) order comparisons.
For a conservative explicit bit bound, use a common denominator equal to the product of the input mass denominators. Its bit length is at most \(L\). Exact score computation, comparisons, and the final budget comparison use integers of \(O(L+\log(m+\ell))\) bits. Using elementary integer arithmetic gives running time
\(O\!\left((m+\tau\min\{q,m\}+m\log m+\ell)(L+\log(m+\ell))^2\right)\).
This is polynomial in the stated input parameters. The committee size \(k\) determines only the index \(k-\ell+1\); no committees or possible ballot types need to be enumerated.
The infimum successful cost is always \(\beta\). It is attained exactly when every fresh candidate precedes \(p\). Otherwise, the successful costs are precisely those strictly greater than \(\beta\).
Thus the equality check is essential for budget feasibility. For example, with one original candidate of score \(1\), one fresh candidate, and \(k=\ell=q=1\), budget \(1\) succeeds exactly when the fresh candidate wins their tie.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated problem correctly. The feasibility criterion, arbitrary tie-breaking condition, explicit construction, and polynomial bit-complexity bound all hold. No major or minor mathematical issues were found.
The definitions are well-posed under the task’s hypotheses:
The argument addresses the specified set \(D\), the ballot-length cap, arbitrary fixed tie-breaking, and real-valued added masses.
Success selects all \(\ell\) fresh candidates and therefore exactly \(r\) original candidates. Thus at least one of the \(r+1\) candidates \(c_1,\ldots,c_{r+1}\) must be excluded. This counting step is valid, including when \(r=0\).
For such an excluded candidate \(e\), the original ordering guarantees \(a(e)\geq t\). Added approvals cannot decrease its score. Every selected fresh candidate must outrank \(e\), so \(z(d)\geq t\) is necessary.
The stricter requirement when \(\pi(d)>\pi(p)\) is also correct. If \(z(d)=t\), then either \(a(e)>t\), or \(a(e)=t\) and \(\pi(e)\leq\pi(p)<\pi(d)\). In either case, \(e\) outranks \(d\), even after adding approvals to \(e\). This contradicts selection of \(d\) and exclusion of \(e\).
These deductions allow arbitrary added approvals to original candidates; they do not assume that a successful addition approves only fresh candidates.
The inequalities \(z(d)\leq x\) and \(\sum_{d\in D}z(d)\leq qx\) follow directly from nonnegative ballot masses and the cap.
Together with the necessary score requirements, they imply
\(\displaystyle x\geq\max\{t,\ell t/q\}=\ell t/h=\beta\).
The identity is correct in both cases \(q\geq\ell\) and \(q<\ell\).
At budget \(b=\beta\), any feasible addition must have \(x=\beta\). The proof correctly shows that every fresh score then equals \(t\):
Consequently, every fresh candidate must precede \(p\). The equality argument remains valid when \(t=0\).
The cyclic construction is valid:
This handles both \(h=1\) and \(h=\ell\). No original candidate receives an added approval.
At equality, every fresh candidate precedes \(p\) and ties its score. Every member of \(T=\{c_1,\ldots,c_r\}\) also outranks \(p\). Every original candidate outside \(T\) ranks at or below \(p\).
Thus all members of \(T\cup D\) outrank all candidates outside that set. Its cardinality is \(k\), so it is exactly the resulting committee. Since \(T\subseteq W\), the task’s replacement condition is satisfied.
For \(b>\beta\), the specified choice
\(\displaystyle s=(t+hb/\ell)/2\)
satisfies \(s>t\), and its cost is \((\beta+b)/2<b\). Fresh candidates then outrank all original candidates outside \(T\) strictly by score. The same committee conclusion follows.
No assumption about the relative ordering of fresh candidates and members of \(T\) is needed.
The decision procedure implements the proved criterion exactly. Comparing \(hb\) with \(\ell a(p)\) avoids any numerical approximation, including at the critical equality boundary.
The arithmetic bound is justified. The product of the input mass denominators has bit length at most \(L\). Since each original score lies in \([0,1]\), its numerator over that denominator also has \(O(L)\) bits. Including the budget and integer factors yields operands of \(O(L+\log(m+\ell))\) bits.
Common-denominator preparation, score accumulation, sorting, and exact budget comparison fit within the stated conservative bound:
\(\displaystyle O\!\left((m+\tau\min\{q,m\}+m\log m+\ell)(L+\log(m+\ell))^2\right)\).
The algorithm uses the listed support, with no enumeration of possible approval types or committees. The role of \(k\) is correctly confined to selecting the index \(k-\ell+1\).
The proof covers zero budget, zero threshold, \(\ell=k\), \(k=m\), and either side of the cap boundary \(q=\ell\). The minimum-versus-infimum statement follows from the established criterion.
The description of the cited result is accurate: [Theorem 2 and its tie-breaking footnote](https://arxiv.org/pdf/2312.11408) give the unrestricted replacement-cost result under tie-breaking benefiting replacement candidates. The present proof is independent of that theorem, so it does not apply its restricted hypotheses to the capped problem.
No additional clarification or repair is required.
⟨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.