Answer: polynomial-time solvable
Theorem 1 — class: algorithmic
Agenda Control for TSMR is in P.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a rational society \(\mu\) over complete rankings of \(C\), and target \(p\), does an agenda \(\triangleright\) exist such that \(p\) is the TSMR winner under the strict pairwise-majority margins induced by \(\mu\)?
Definitions. A rational preference distribution is given explicitly by rational masses on complete rankings of a finite candidate set C. For any distribution ν, let a strictly beat b when ν(a≻b)>ν(b≻a). Given agenda ▷, form arcs a→b exactly when a▷b and a strictly beats b; the TSMR winner is the rightmost candidate with no incoming arc.
Target. Given C, μ, p, ▷, and rational β≥0, is deciding whether some nonnegative distribution y over rankings, of total mass β, makes p the TSMR winner under μ+y solvable in polynomial time, or NP-hard?
Nearest known results. The discrete coalition-manipulation version, with an explicitly listed voter multiset and an integer number of added voters, is polynomial-time solvable for TSMR. No result for the exact rational-mass version above is assumed here.
The decision problem is solvable in deterministic polynomial time.
More strongly, if any distribution of coalition mass $\beta$ makes $p$ the TSMR winner, then assigning all mass $\beta$ to one explicitly constructible ranking also makes $p$ win.
Write the agenda as
$$ c_1 \mathbin{\triangleright} c_2 \mathbin{\triangleright}\cdots \mathbin{\triangleright} c_m, $$
and let $p=c_k$. For any nonnegative measure $\nu$ on complete rankings, define
$$ \Delta_\nu(a,b)=\nu(a\succ b)-\nu(b\succ a). $$
Thus $\Delta_\nu(a,b)=-\Delta_\nu(b,a)$, and there is an arc $c_i\to c_j$ precisely when
$$ i<j \quad\text{and}\quad \Delta_\nu(c_i,c_j)>0. $$
Margins are additive:
$$ \Delta_{\mu+y}(a,b)=\Delta_\mu(a,b)+\Delta_y(a,b). $$
Candidate $p=c_k$ is the TSMR winner under $\nu$ if and only if both of the following hold:
$$ \Delta_\nu(p,c_i)\ge 0. $$
$$ \Delta_\nu(c_i,c_j)>0. $$
The first condition says that no agenda predecessor $c_i$ strictly beats $p$. Hence there is no incoming arc into $p$.
The second condition says that every candidate strictly to the right of $p$ has at least one incoming arc. Consequently, no candidate to the right of $p$ is eligible to be the rightmost candidate with no incoming arc.
Therefore, $p$ has no incoming arc and every candidate to its right has one, so $p$ is exactly the rightmost candidate with no incoming arc.
Conversely, if $p$ is the TSMR winner, it must have no incoming arc, giving the first condition. Every candidate to its right must have an incoming arc, since otherwise such a candidate would be a later candidate with no incoming arc. This gives the second condition. $\square$
Define the complete ranking
$$ R^\star: \quad p\succ c_1\succ\cdots\succ c_{k-1} \succ c_{k+1}\succ\cdots\succ c_m. $$
Thus $p$ is placed first, and all other candidates retain their agenda order. Let $y^\star$ assign all coalition mass $\beta$ to $R^\star$.
For an arbitrary coalition distribution $y$ of total mass $\beta$ and any distinct $a,b$,
$$ \Delta_y(a,b) = y(a\succ b)-y(b\succ a) \le y(a\succ b)+y(b\succ a) =\beta. $$
If $R^\star$ ranks $a$ above $b$, then
$$ \Delta_{y^\star}(a,b)=\beta\ge\Delta_y(a,b). $$
If some coalition distribution $y$ of total mass $\beta$ makes $p$ win, then $y^\star$ also makes $p$ win.
Suppose $\mu+y$ makes $p$ win.
For every $i<k$, the canonical ranking places $p$ above $c_i$. Hence
$$ \Delta_{\mu+y^\star}(p,c_i) = \Delta_\mu(p,c_i)+\beta \ge \Delta_\mu(p,c_i)+\Delta_y(p,c_i) = \Delta_{\mu+y}(p,c_i) \ge 0. $$
Thus $p$ has no incoming arc under $\mu+y^\star$.
Now fix $j>k$. Since $p$ wins under $\mu+y$, Lemma 1 supplies some $i<j$ satisfying
$$ \Delta_{\mu+y}(c_i,c_j)>0. $$
The canonical ranking places $c_i$ above $c_j$: this is immediate if $c_i=p$, while otherwise both candidates occur in agenda order after $p$ in $R^\star$. Therefore,
$$ \Delta_{\mu+y^\star}(c_i,c_j) = \Delta_\mu(c_i,c_j)+\beta \ge \Delta_\mu(c_i,c_j)+\Delta_y(c_i,c_j) = \Delta_{\mu+y}(c_i,c_j) >0. $$
The same $c_i$ therefore supplies an incoming arc into $c_j$ under $\mu+y^\star$. This holds for every $j>k$. Lemma 1 now implies that $p$ wins under $\mu+y^\star$. $\square$
Notice that the argument preserves the necessary distinction between weak and strict comparisons: margins preventing arcs into $p$ need only remain nonnegative, whereas every positive witness margin for a later candidate remains strictly positive.
By Lemma 2, a successful manipulation exists if and only if the canonical manipulation succeeds. Equivalently, the answer is yes precisely when
$$ \Delta_\mu(p,c_i)+\beta\ge 0 \qquad\text{for every }i<k, $$
and
$$ \text{for every }j>k,\quad \text{there exists }i<j\text{ such that } \Delta_\mu(c_i,c_j)+\beta>0. $$
Suppose $\mu$ is listed using $s$ rankings with binary-encoded rational masses. All pairwise margins can be computed in $O(sm^2)$ rational arithmetic operations by processing each listed ranking and each candidate pair. Checking the displayed conditions then takes $O(m^2)$ further comparisons.
Sums and comparisons of polynomially many binary-encoded rational numbers have polynomial bit complexity: a common denominator formed from the input denominators has bit length at most the sum of their bit lengths, and all required integer additions, multiplications, and sign tests therefore involve polynomially many bits. No enumeration of the $m!$ possible rankings is required.
The cases $\beta=0$, $k=1$, and $k=m$ are covered directly by the same conditions.
Continuous rational-mass coalition manipulation for TSMR is polynomial-time solvable. A successful coalition never needs to split its mass among different rankings: placing all mass on $R^\star$ is optimal for every pairwise condition relevant to making $p$ win.
⟨structured verdict parsed — rendered above⟩
The prover fully resolves the target by giving a deterministic polynomial-time decision criterion. The stronger claim—that any successful coalition distribution can be replaced by a single canonical ranking carrying all mass $\beta$—is correctly established.
$$
y(a\succ b)+y(b\succ a)=\beta,
$$
and hence $\Delta_y(a,b)\le\beta$. When the canonical ranking places $a$ above $b$, its contribution is exactly $\beta$.
Consequently, the canonical contribution $\beta$ is at least the original contribution, preserving the strict positivity of the witness margin.
No unjustified mathematical step, missing hypothesis, or incorrect strict/weak inequality was found.
⟨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.