Answer: —
Theorem 2 — class: algorithmic
AV-$AddApprovals-CI-Bribery ∈P.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate/day axis \(C\), committee size \(k\), target \(p\), a finite set of interval-booking types \(T\), masses \(\mu_t\), initial intervals \(I_t\subseteq C\), and per-addition costs \(q_t(c)\), allocate each \(\mu_t\) among interval extensions \(J\supseteq I_t\) so as to minimize total cost subject to \(p\) belonging to a top-\(k\) approval committee in the resulting mass society.
Days are ordered \(1,\ldots,m\). A type \(t\) has rational mass \(w_t\), an initial nonempty interval \([a_t,b_t]\), and nonnegative rational costs \(c_{t,d}\) for adding each day \(d\notin[a_t,b_t]\).
Any portion of a type’s mass may be assigned a final interval \([a',b']\supseteq[a_t,b_t]\); its cost is its mass times \(∑_{d\in[a',b']\setminus[a_t,b_t]}c_{t,d}\). A day’s approval score is the total mass whose final interval contains it.
A top-\(k\) approval committee is any \(k\) days of maximum total score; thus \(p\) is eligible iff fewer than \(k\) days have score strictly greater than \(p\).
Is computing the minimum total cost that makes \(p\) eligible for a top-\(k\) committee solvable in polynomial time, or is its budget decision version NP-hard?
For finite individual voters, constructive individually priced approval-addition bribery with a fixed candidate-interval axis is in P.
The general binary-encoded rational-mass problem is not completely classified here. However, the following statements are proved:
The remaining obstacle is the cardinality disjunction selecting which at most $k-1$ days may beat $p$.
Let
$$ I_t=[a_t,b_t] $$
be the initial interval of type $t$.
For a type whose initial interval does not contain $p$, define its minimal extension to $p$ by
$$ J_t= \begin{cases} [b_t+1,p],&b_t<p,\\ [p,a_t-1],&a_t>p. \end{cases} $$
Thus $J_t$ is precisely the set of newly approved days when $I_t$ is extended minimally to include $p$. Define its per-unit cost by
$$ \gamma_t=\sum_{d\in J_t}c_{t,d}. $$
There is an optimal bribery with the following form:
Consider any portion of any type assigned a final interval $K\supseteq I_t$.
If $p\notin K$, replace $K$ by $I_t$. This does not change $p$'s score, can only decrease other scores, and cannot increase cost because all addition costs are nonnegative.
If $p\in K$, replace $K$ by the smallest interval containing $I_t\cup\{p\}$. Again, $p$ remains approved, no other score increases, and the cost cannot increase.
For a type already approving $p$, the latter smallest interval is just $I_t$, so changing this type is unnecessary.
After applying these replacements to every portion, all bribed portions of type $t$ use the same minimal extension. Aggregating their masses gives one variable $x_t$. Since competitors' scores only decrease under the transformation while $p$'s score is unchanged, eligibility is preserved. Hence an optimum of this form exists. $\square$
Let the initial score of day $d$ be
$$ s_d^0=\sum_{t:d\in I_t}w_t. $$
Let $T'$ denote the types not initially approving $p$. Under a canonical bribery $x=(x_t)_{t\in T'}$,
$$ s_p(x)=s_p^0+\sum_{t\in T'}x_t $$
and, for $d\ne p$,
$$ s_d(x)=s_d^0+\sum_{t:d\in J_t}x_t. $$
Define
$$ A_{d,t}= \begin{cases} 1,&d\notin J_t,\\ 0,&d\in J_t, \end{cases} \qquad \Delta_d=s_d^0-s_p^0. $$
Then
$$ s_p(x)-s_d(x) = -\Delta_d+\sum_{t\in T'}A_{d,t}x_t. $$
Consequently, day $d$ does not beat $p$ exactly when
$$ \sum_{t\in T'}A_{d,t}x_t\ge\Delta_d. \tag{1} $$
The cost is
$$ \sum_{t\in T'}\gamma_t x_t. \tag{2} $$
Let $C=\{1,\ldots,m\}\setminus\{p\}$.
A canonical bribery $x$ makes $p$ eligible if and only if there is a set $H\subseteq C$ with $|H|\le k-1$ such that (1) holds for every $d\in C\setminus H$.
If $p$ is eligible, the set
$$ H_0=\{d\in C:s_d(x)>s_p(x)\} $$
has size at most $k-1$. Taking $H=H_0$ proves the forward implication.
Conversely, if (1) holds outside some $H$ of size at most $k-1$, then only days in $H$ can have score strictly greater than $p$. Hence fewer than $k$ days beat $p$, so $p$ is eligible. $\square$
For a fixed $H$, the minimum cost is therefore the linear program
$$ \begin{aligned} \text{minimize}\quad& \sum_{t\in T'}\gamma_t x_t,\\ \text{subject to}\quad& \sum_{t\in T'}A_{d,t}x_t\ge\Delta_d &&\text{for every }d\in C\setminus H,\\ &0\le x_t\le w_t &&\text{for every }t\in T'. \end{aligned} \tag{LP$_H$} $$
This LP has rational data and polynomial size.
The problem is solvable in time
$$ \binom{m-1}{k-1}\operatorname{poly}(|I|), $$
where $|I|$ is the binary input length.
In particular, it is polynomial-time solvable for every fixed $k$, and also whenever $m-k$ is fixed.
It suffices to enumerate all sets $H$ of size exactly $k-1$ and solve $\mathrm{LP}_H$. A smaller exceptional set can always be enlarged without invalidating the constraints. Since
$$ \binom{m-1}{k-1}=\binom{m-1}{m-k}, $$
the stated fixed-parameter special cases follow. $\square$
For $k=1$, there is no disjunction: one simply enforces (1) for every opponent and solves one LP.
The budget decision version belongs to NP.
A nondeterministic algorithm guesses a set $H\subseteq C$ with $|H|\le k-1$. It then adds the budget constraint
$$ \sum_t\gamma_t x_t\le B $$
to $\mathrm{LP}_H$ and tests rational LP feasibility in deterministic polynomial time.
By Lemma 2, some guessed set produces a feasible LP exactly when a budget-feasible bribery making $p$ eligible exists. $\square$
The fixed-$H$ LP has additional useful structure.
Call a type left if $b_t<p$ and right if $a_t>p$. Order the opponent rows as follows:
For a left type $t$,
$$ A_{d,t}=1 $$
for every right day and for precisely those left days satisfying $d\le b_t$. Thus the ones in its column form a suffix in the displayed row order.
For a right type $t$,
$$ A_{d,t}=1 $$
for every left day and for precisely those right days satisfying $d\ge a_t$. Thus the ones form a prefix.
Hence every column of $A$ has consecutive ones. Restricting to the rows outside $H$ preserves this property.
A $0$-$1$ matrix with the consecutive-ones property in its columns is totally unimodular. Appending the bound rows $I$ and $-I$ preserves total unimodularity.
Let $D$ be a common denominator of the masses $w_t$. There is an optimal bribery in which every $x_t$ is an integer multiple of $1/D$.
The numbers
$$ Dw_t,\qquad D\Delta_d $$
are integers. Substitute $X_t=Dx_t$ in $\mathrm{LP}_H$. Its constraint matrix consists of $A$, $I$, and $-I$, and is totally unimodular by the preceding argument. Its right-hand side is integral. Therefore every vertex of the resulting bounded feasible polyhedron is integral.
For each $H$, a linear objective has an optimal vertex whenever the LP is feasible. Hence $\mathrm{LP}_H$ has an optimum with integral $X_t$, equivalently with $x_t\in(1/D)\mathbb Z$.
Finally, choose an exceptional set attaining the global minimum over all $H$. Its integral-grid optimum is also globally optimal. $\square$
Replace every type $t$ by
$$ W_t=Dw_t $$
identical atomic voters of mass $1/D$. Proposition 5 shows that some optimum bribes an integral number of these atoms from every type. Thus this atomized instance has exactly the same optimum as the continuous instance.
The known finite-voter candidate-interval algorithm enumerates the numbers of bribed voters on the two sides of $p$ and uses dynamic programming along the candidate axis; see Theorem 2 of [Kusek, Bredereck, Faliszewski, Kaczmarczyk, and Knop](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p1725.pdf).
Its application here is polynomial in
$$ N=\sum_t W_t=D\sum_t w_t, $$
in $m$, and in the remaining input length. It is therefore exact but only pseudo-polynomial for the rational-mass representation: $N$ can be exponentially large in the binary encoding of the denominators.
This also pinpoints why the cited finite-voter result does not by itself prove polynomial-time solvability of the stated problem.
For unrestricted $k$, the feasible region is the union of the polyhedra $\mathrm{LP}_H$ over exponentially many exceptional sets. Total unimodularity settles each member of the union but does not optimize over the union in polynomial time.
A complete classification requires one of the following:
Neither is proved above. In particular, merely expanding rational mass into individual voters is not a polynomial-time reduction because the expanded electorate may have exponential size.
⟨structured verdict parsed — rendered above⟩
The output establishes several correct structural and parameter-restricted results, but it does not answer the target classification: it proves neither a polynomial-time algorithm for unrestricted $k$ nor NP-hardness of the budget decision problem. Its self-description as a partial classification is accurate.
The canonicalization, LP formulation, fixed-parameter special cases, NP membership, and total-unimodularity argument are substantively correct. The pseudo-polynomial consequence is plausible and supported by the cited theorem, but its reduction to the finite-voter setting needs a few routine details stated explicitly.
Lemma 1 is correct.
There is a minor formal ambiguity in the phrase “apply these replacements to every portion.” The model does not specify whether an allocation may use infinitely many portions or how such an allocation is represented. The argument is immediate for a finite split, but the admissible representation should be stated or the aggregation operation formalized.
The score equations are correct.
For a type not initially approving $p$, extending mass $x_t$ minimally to $p$:
Therefore its contribution to $s_p(x)-s_d(x)$ is $x_t$ precisely when $d\notin J_t$. This validates the coefficient $A_{d,t}$ and the identity
$$ s_p(x)-s_d(x) = -\Delta_d+\sum_t A_{d,t}x_t. $$
Consequently, inequality (1) is exactly equivalent to $s_d(x)\le s_p(x)$. Ties are handled correctly because eligibility excludes only days with strictly greater scores.
Lemma 2 is correct.
For fixed $H$, $\mathrm{LP}_H$ therefore computes the correct minimum among canonical briberies with no beating day outside $H$.
Corollary 3 is correct, under the standard implicit condition $1\le k\le m$.
Enumerating sets of size exactly $k-1$ suffices because any smaller exceptional set can be enlarged. The number of LPs is
$$ \binom{m-1}{k-1} = \binom{m-1}{m-k}. $$
Thus the algorithm is polynomial for each fixed $k$ and for each fixed $m-k$. This is an XP-style bound with the relevant parameter fixed, not a fixed-parameter tractability claim; the output does not incorrectly claim otherwise.
Proposition 4 is correct.
A certificate need contain only $H$, whose description has polynomial length. Once $H$ is given, rational LP feasibility with the budget constraint is decidable in deterministic polynomial time. Lemma 2 supplies the required equivalence.
No rational vector $x$ needs to be included explicitly in the certificate because the verifier may run a polynomial-time LP algorithm.
The stated row ordering and column descriptions are correct.
The invoked theorem that a $0$-$1$ matrix with consecutive ones in every column is totally unimodular is applicable. Adding unit bound rows preserves total unimodularity.
After substituting $X_t=Dx_t$, the right-hand sides $D\Delta_d$ and $Dw_t$ are integral. Hence each nonempty bounded fixed-$H$ polyhedron has an integral optimal vertex. Selecting an $H$ attaining the minimum then gives the claimed global $1/D$-grid optimum.
The cited [Theorem 2](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p1725.pdf) does establish polynomial-time solvability of individually priced approval-addition bribery for finite candidate-interval elections. Its algorithm guesses the numbers of bribed voters on the two sides of $p$ and uses dynamic programming along the candidate axis, as claimed.
However, the application is not fully written out. The output should explicitly specify:
These are routine scaling and representation details and do not undermine the substantive claim, but they are necessary for a fully verifiable invocation of the external result.
Subject to those clarifications, the running time is polynomial in the expanded voter count
$$ N=\sum_t Dw_t $$
and hence can be exponential in the original binary input length. The warning that explicit atomization does not yield a bit-polynomial algorithm is correct.
The decisive deficiency is explicit in Section 8: the unrestricted case remains unresolved.
The user asked for a classification between polynomial-time solvability and NP-hardness of the budget decision problem. The output supplies neither. Membership in NP, polynomial solvability for fixed $k$ or fixed $m-k$, and a pseudo-polynomial algorithm do not decide the unrestricted binary-encoded problem.
The existing structural results can remain after the two minor clarifications above. To resolve the assigned task, the prover must additionally supply and verify either:
Merely restating the exponential union of LPs or the atomized finite-voter algorithm does not close this gap.
⟨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.