Campaign Management under Approval-Driven Voting Rules

NEW RESULT — discrete: hard → continuous: polynomial-time · adversarial review: proved_with_minor_gaps

Answer: Polynomial-time solvable: $\mathrm{P}$, with running time polynomial in $m,\tau,L$, even for arbitrary strict rankings.

The anchor (named result in the paper)

statement extracted from the paper’s text layer; consult the paper for the exact wording

The continuous mirror question, as graded

Given candidates $C$, an axis $\triangleleft$, a finite set of single-peaked voter types $t=(\succ_t,\ell_t)$, rational masses $\mu_t$ with $\sum_t\mu_t=1$, and target $p$, choose $x_{t,k}\ge0$ with $\sum_k x_{t,k}=\mu_t$ to minimize $\sum_{t,k}|k-\ell_t|x_{t,k}$, subject to $p$ being an SP-AV winner after the mass transfer; equivalently, decide whether a transfer of cost at most $B$ exists.

Packaged proof task (what the prover saw — nothing else)

Given a nonempty candidate set $C$ of size $m$, a linear axis $\triangleleft$, and a target $p\in C$, consider types $t=(\succ_t,\ell_t)$, where $\succ_t$ is a strict total ranking single-peaked on the supplied axis and $\ell_t\in\{0,\ldots,m\}$.
A society is given by its support: the list of the $\tau$ types with positive mass, each with its mass $\mu_t$ as a binary rational, with $\sum_t\mu_t=1$. Here $\tau$ is the support size, not the number of possible types; let $L$ be the total input bit length.
A transfer chooses real masses $x_{t,k}\geq0$, for $k\in\{0,\ldots,m\}$, with $\sum_{k=0}^m x_{t,k}=\mu_t$. This mass retains ranking $\succ_t$ and approves its top $k$ candidates; both increases and decreases of approval counts are allowed.
Its cost is $\sum_t\sum_{k=0}^m |k-\ell_t|x_{t,k}$. Under SP-AV, candidates with maximum total approving mass are winners, including all ties; empty and full approval sets are permitted without adjustment.
Given a nonnegative binary rational budget $B$, decide whether a transfer of cost at most $B$ makes $p$ a winner.

Is this continuous SP-AV support-bribery decision problem in $\mathrm{P}$, with running time polynomial in $m,\tau,L$, or is it NP-hard?

For indivisible voters, support bribery with these unit costs is NP-hard even with single-peaked rankings ([source](https://arxiv.org/pdf/1501.00387)). No result settling exactly this divisible-mass problem was located in the literature search.

Modeling choices made when packaging the task

Prover output (gpt-6.1-sol / high, Bolzano prover prompt)

Result

The problem is in $\mathrm{P}$, with running time polynomial in $m,\tau,L$. In fact, the same algorithm works for arbitrary strict rankings: single-peakedness is unnecessary.

An exact linear formulation

Let $T$ be the supplied support, so $|T|=\tau$. For each $t\in T$, let $r_t(c)\in\{1,\ldots,m\}$ be the position of candidate $c$ in $\succ_t$. Define $a_{t,k,c}$ to equal $1$ when $r_t(c)\leq k$, and $0$ otherwise.

Thus $a_{t,k,c}$ records whether mass of type $t$ transferred to approval count $k$ approves $c$. In particular, $a_{t,0,c}=0$ and $a_{t,m,c}=1$, as required by the stipulated treatment of empty and full approval sets.

Introduce a real variable $x_{t,k}$ for every $t\in T$ and $k\in\{0,\ldots,m\}$. Consider the following linear feasibility problem:

Nonnegativity: $x_{t,k}\geq0$ for every $t,k$.
Conservation of each original type’s mass: $\sum_{k=0}^{m}x_{t,k}=\mu_t$ for every $t\in T$.
Winner conditions: $\sum_{t\in T}\sum_{k=0}^{m}(a_{t,k,p}-a_{t,k,c})x_{t,k}\geq0$ for every $c\in C\setminus\{p\}$.
Budget: $\sum_{t\in T}\sum_{k=0}^{m}|k-\ell_t|x_{t,k}\leq B$.

The quantities $|k-\ell_t|$ are fixed integer coefficients, so the budget constraint is linear.

Proof of equivalence

Suppose first that a successful transfer of cost at most $B$ exists. Use its transferred masses as the variables $x_{t,k}$. Nonnegativity and conservation hold by the definition of a transfer.

The resulting approving mass of candidate $c$ is exactly

$\displaystyle S_c(x)=\sum_{t\in T}\sum_{k=0}^{m}a_{t,k,c}x_{t,k}.$

Because all candidates attaining the maximum score are winners, $p$ is a winner precisely when $S_p(x)\geq S_c(x)$ for every $c\neq p$. These are exactly the winner constraints. The transfer’s stated cost is exactly the left-hand side of the budget constraint. Consequently, the linear system is feasible.

Conversely, suppose the linear system has a real solution. For every original type $t$, assign mass $x_{t,k}$ to approval count $k$, retaining ranking $\succ_t$. Nonnegativity and conservation make this an allowed transfer. Its candidate scores are the quantities $S_c(x)$ above, so the winner constraints make $p$ a winner. The budget constraint ensures cost at most $B$.

Therefore the instance is a yes-instance if and only if the linear system is feasible.

Polynomial running time and exactness

There are $N=\tau(m+1)$ variables. Besides nonnegativity, there are $\tau$ conservation equalities, $m-1$ winner inequalities, and one budget inequality. Replacing each equality by two inequalities gives $2\tau+m$ inequalities besides nonnegativity.

Every left-hand coefficient is an integer of absolute value at most $m$: conservation coefficients are $0$ or $1$, winner coefficients belong to $\{-1,0,1\}$, and cost coefficients lie in $\{0,\ldots,m\}$. The right-hand sides are the supplied rational masses, the rational budget, and zeros. Hence the entire system has binary encoding length polynomial in $m,\tau,L$, and its coefficients can be constructed in polynomial time from the supplied rankings.

The polynomial-time theorem for rational linear programming decides feasibility of an explicitly given rational linear system over the reals, in time polynomial in its binary encoding length. Thus it applies directly here, including when the feasible region has lower dimension or success requires exact ties or exact budget equality. See [Gács and Lovász, *Khachiyan’s linear programming algorithm*](https://www.sciencedirect.com/science/article/pii/0196677480900024).

This proves the claimed polynomial running time. The formulation is exact for divisible mass; it imposes no integrality restrictions corresponding to indivisible voters.

⟨structured verdict parsed — rendered above⟩

Adversarial review (gpt-6.1-sol / medium, Bolzano verifier prompt)

Overall assessment

The argument establishes polynomial-time solvability of the continuous problem. Its linear formulation is exact, both directions of the equivalence are correct, and the input-size analysis supports the claimed running time polynomial in $m,\tau,L$.

The only issue identified is a minor bibliographic mismatch in the citation for polynomial-time linear programming. No mathematical repair or additional lemma is needed.

Step-by-step verification

1. Variables and approval coefficients

The supplied support $T$, rather than the universe of possible types, is correctly used to index variables. There are exactly $\tau(m+1)$ variables.

Because each ranking is strict and total, every position $r_t(c)$ is well-defined. The coefficient $a_{t,k,c}$ correctly records whether candidate $c$ belongs to the top $k$ candidates of type $t$.

The endpoint definitions are correct: $k=0$ approves nobody, and $k=m$ approves everybody. These match the task’s explicit permission for empty and full approval sets without adjustment.

Finding: Correct, with no missing assumptions.

2. Transfer constraints and cost

Nonnegativity and the equalities
$$ \sum_{k=0}^{m}x_{t,k}=\mu_t $$
are exactly the requirements imposed on transferred masses. They permit arbitrary division of each original type’s mass and preserve its ranking.

The coefficient $|k-\ell_t|$ is fixed by the input and the destination approval count. Consequently, the budget constraint is linear and equals the cost specified in the task. Both increases and decreases are included.

Finding: Correct. No restriction to indivisible voters or one-directional changes has been introduced.

3. Winner constraints

The score expression
$$ S_c(x)=\sum_{t\in T}\sum_{k=0}^{m}a_{t,k,c}x_{t,k} $$
counts precisely the total approving mass of candidate $c$.

Since all maximum-score candidates are winners, the condition that $p$ wins is exactly $S_p(x)\geq S_c(x)$ for every competing candidate $c$. The proposed constraints express these comparisons with the correct sign. Non-strict inequalities correctly permit ties.

Finding: Correct.

4. Forward implication

For an allowed successful transfer, substituting its masses into the variables satisfies nonnegativity and conservation by definition. The score calculation establishes all winner constraints, and the cost calculation establishes the budget constraint.

Finding: Every required constraint follows directly from the assumed transfer.

5. Reverse implication

A real feasible solution assigns a nonnegative mass to every permitted approval count, with each original type’s mass conserved. This is an allowed transfer under the task’s definition.

Its scores and cost are exactly those in the linear constraints. Therefore $p$ is a winner and the cost is at most $B$.

Finding: Correct. The use of real solutions is explicitly authorized by the task, so no integrality or rationality requirement is missing.

6. Constraint count and encoding length

The counts are correct:

$\tau$ conservation equalities become $2\tau$ inequalities.
There are $m-1$ winner inequalities.
There is one budget inequality.

Thus there are $2\tau+m$ inequalities besides nonnegativity.

The coefficient bounds are also correct. Conservation coefficients have absolute value at most one, winner coefficients belong to $\{-1,0,1\}$, and cost coefficients are integers between zero and $m$. Negating conservation rows when converting equalities preserves these bounds.

The right-hand sides consist of supplied rational masses and budget, their negatives where needed, and zeros. An explicit matrix with these dimensions and coefficient sizes has encoding length polynomial in $m,\tau,L$. The supplied rankings suffice to construct all coefficients in polynomial time.

Finding: Correct. There is no enumeration of exponentially many possible types.

7. Polynomial-time feasibility theorem

The prover states the relevant theorem precisely enough: feasibility of an explicitly represented rational linear system over the reals can be decided in time polynomial in its binary encoding length.

Its hypotheses are satisfied here: the system has finitely many variables and constraints, all coefficients are rational, and the explicit encoding length is polynomially bounded. The theorem does not require a full-dimensional feasible region or strict feasibility. Thus exact ties and budget equality do not invalidate its application.

The linked publication supports polynomial-time feasibility, but its authors are Bengt Aspvall and Richard E. Stone, whereas the prover attributes it to Gács and Lovász. See the [linked publication’s bibliographic record](https://www.sciencedirect.com/science/article/pii/0196677480900024).

Minor issue: Correct the authors of the linked reference, or provide the intended Gács–Lovász reference. This is a citation correction, not a missing mathematical justification.

8. Edge cases and scope

For $m=1$, there are no competing candidates, so the empty collection of winner constraints correctly represents automatic winner status for $p$.

For $B=0$, the nonnegative cost constraint correctly enforces zero total cost. No step assumes positive budget.

The support is nonempty because its positive masses sum to one. The formulation covers all permitted original approval counts, including zero and $m$.

Finally, no step uses single-peakedness or the axis. The stronger claim for arbitrary strict rankings therefore follows from the written argument.

Finding: All relevant edge cases and the claimed extension are handled.

Required feedback

Correct the bibliographic attribution of the linear programming reference. No additional proof steps, lemmas, or computational checks are required.