Answer: Computing \(\operatorname{OPT}\) is possible in time polynomial in \(m,\tau,L\); the budget problem is in \(\mathrm{P}\).
Theorem 5 — class: hardness
Given candidates \(C\), target \(p\), and a finite support of types \(t=(B_t,\rho_t)\) with rational masses \(\mu_t>0\) summing to \(1\), where \(B_t\in\binom{C}{3}\) is the type’s bottom-three set and \(\rho_t\) its bribery price, minimize \(\sum_t \rho_t\sum_{S\in\binom{C}{3},\,S\ne B_t} y_{t,S}\) over \(y_{t,S}\ge 0\), subject to \(\sum_{S\in\binom{C}{3}}y_{t,S}=\mu_t\) for every \(t\) and \(\sum_{t,S:\,p\in S}y_{t,S}\le\sum_{t,S:\,c\in S}y_{t,S}\) for every \(c\in C\).
Let \(C\) be a candidate set with \(m=|C|\ge 3\) and preferred candidate \(p\in C\). Under 3-Veto, candidates with minimum veto mass win; ties are allowed, so making \(p\) a co-winner suffices.
A society is given by its support: a list of \(\tau\) types \(t=(B_t,\rho_t)\) with positive binary rational masses \(\mu_t\) summing to \(1\), where \(B_t\in\binom{C}{3}\) and \(\rho_t\) is a nonnegative binary integer price per unit of changed mass. Here \(\tau\) is the support size, not the number of possible types.
Mass is arbitrarily divisible. Any portion of a type may be assigned any bottom-three set, at price \(\rho_t\) per unit if that set differs from \(B_t\); retaining \(B_t\) costs zero. Every such set represents an admissible strict ranking.
For real variables \(y_{t,S}\ge 0\), define the minimum bribery cost as \(\operatorname{OPT}=\min\sum_t\rho_t\sum_{S\in\binom{C}{3},\,S\ne B_t}y_{t,S}\), subject to \(\sum_{S\in\binom{C}{3}}y_{t,S}=\mu_t\) for every type and \(\sum_{t,S:\,p\in S}y_{t,S}\le\sum_{t,S:\,c\in S}y_{t,S}\) for every \(c\in C\).
The budget version additionally receives a nonnegative binary rational \(K\) and asks whether \(\operatorname{OPT}\le K\). Let \(L\) be the total binary input length, including masses, prices, and budget.
Is computing \(\operatorname{OPT}\) possible in time polynomial in \(m,\tau,L\), or is deciding whether \(\operatorname{OPT}\le K\) NP-hard?
For indivisible, unweighted voters with nonnegative integer prices and budget, constructive priced 3-Veto bribery allowing co-winners is NP-complete. This discrete result does not classify the divisible-mass problem.
Computing \(\operatorname{OPT}\) is possible in time polynomial in \(m,\tau,L\). The budget problem is therefore in \(\mathrm{P}\).
The crucial observation is that there are only \(\binom{m}{3}\) possible bottom-three sets. Thus the linear program in the question already has polynomial size.
Let \(\mathcal S=\binom{C}{3}\) and \(N=|\mathcal S|=\binom{m}{3}\). Enumerate these sets and introduce one nonnegative variable \(y_{t,S}\) for every type \(t\) and every \(S\in\mathcal S\). There are \(n=\tau N\le \tau m^3\) variables.
Define the integer objective coefficients by
\[
a_{t,S}=
\begin{cases}
0,&S=B_t,\\
\rho_t,&S\ne B_t.
\end{cases}
\]
The objective is \(\sum_{t,S}a_{t,S}y_{t,S}\).
For each type, impose the mass-preservation equality
\[
\sum_{S\in\mathcal S}y_{t,S}=\mu_t.
\]
For every \(c\in C\setminus\{p\}\), impose
\[
\sum_{t,S}
\bigl(\mathbf 1_{\{p\in S\}}-\mathbf 1_{\{c\in S\}}\bigr)y_{t,S}\le 0.
\]
Here \(\mathbf 1_{\{q\in S\}}\) equals one when \(q\in S\), and zero otherwise. These inequalities say exactly that the veto mass of \(p\) is no greater than that of any other candidate.
Consequently, feasible solutions are precisely the allowed mass assignments making \(p\) a co-winner, and their objective values are precisely their bribery costs. Arbitrary divisibility is what permits the variables to be real rather than integer.
For every \(m\ge 3\), consider the assignment
\[
y_{t,S}=\frac{\mu_t}{N}
\qquad(t,\ S\in\mathcal S).
\]
It preserves each type’s mass. Every candidate belongs to exactly \(\binom{m-1}{2}\) bottom-three sets, so every candidate receives veto mass
\[
\sum_t\frac{\mu_t}{N}\binom{m-1}{2}
=\frac{\binom{m-1}{2}}{\binom{m}{3}}
=\frac{3}{m}.
\]
Thus this assignment is feasible.
Moreover, nonnegativity and mass preservation imply \(0\le y_{t,S}\le\mu_t\). The feasible set is therefore bounded; it is also closed because it is defined by finitely many linear equalities and inequalities. A linear objective attains its minimum on this nonempty compact set. In particular, \(\operatorname{OPT}\) exists and is finite.
For the degenerate case \(m=3\), the unique bottom-three set is \(C\), so all candidates always tie and \(\operatorname{OPT}=0\). The same algorithm applies to every \(m\ge4\).
We use the standard polynomial-time theorem for rational linear programming: an explicitly represented linear program with rational coefficients can be solved in time polynomial in its total binary encoding length; when feasible with a finite optimum, an exact rational optimal solution and objective value can be returned.
Its hypotheses hold here:
Even a dense representation has encoding length bounded by
\[
O\!\left(n(\tau+m+L)+\tau L\right),
\]
which is polynomial in \(m,\tau,L\). Enumerating the triples and constructing this representation also takes polynomial time.
The rational linear-programming theorem therefore computes the exact value of \(\operatorname{OPT}\) in the required polynomial time. For the budget version, comparing this exact rational value with the input rational \(K\) is a polynomial-time operation.
The cited hardness for indivisible voters does not transfer: the divisible problem permits fractional allocations and is exactly the polynomial-size linear program above.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the task. It establishes polynomial-time computation of the exact optimum and polynomial-time decision of the budget problem. No major or minor issues were found.
The count \(N=\binom{m}{3}\) is correct. Because each bottom set has fixed size three, enumerating all such sets takes polynomial time in \(m\). The resulting number of variables, \(n=\tau N\le \tau m^3\), is polynomial in the required parameters.
The construction uses the actual support size \(\tau\), as required, and does not confuse it with the number of possible types.
The objective coefficients correctly distinguish retaining \(B_t\), which costs zero, from assigning any other set, which costs \(\rho_t\) per unit. This also handles types with zero price.
The mass-preservation equalities and nonnegativity constraints precisely describe the permitted allocations of each type’s mass.
For each \(c\ne p\), the stated inequality is exactly the veto mass of \(p\) minus the veto mass of \(c\), constrained to be nonpositive. Its sign is correct for 3-Veto, where minimum veto mass wins. Omitting the constraint for \(c=p\) removes only the tautology \(0\le 0\).
The task explicitly permits every bottom-three set and arbitrary divisibility. Thus no ranking-realizability constraint or integrality condition is missing. The claimed correspondence between feasible solutions, successful bribery assignments, and their costs is valid.
The uniform assignment \(y_{t,S}=\mu_t/N\) is nonnegative and sums to \(\mu_t\) for each type.
The count \(\binom{m-1}{2}\) of triples containing a fixed candidate is correct. Using \(\sum_t\mu_t=1\), the displayed calculation gives veto mass \(3/m\) for every candidate. Therefore all candidates tie, and \(p\) is a co-winner.
This reasoning applies throughout the stated domain \(m\ge 3\).
The bound \(0\le y_{t,S}\le\mu_t\) follows directly from nonnegativity and each type’s mass equality. The feasible set is closed and bounded in a finite-dimensional real space and is nonempty by the preceding construction.
The linear objective is continuous, so it attains a finite minimum on this compact set. The existence claim is justified.
When \(m=3\), the only bottom-three set is \(C\), necessarily equal to every \(B_t\). All candidates receive veto mass one, and every objective coefficient is zero. The claimed value \(\operatorname{OPT}=0\) is correct.
The rational linear-programming theorem is stated sufficiently precisely: explicitly encoded rational LPs admit polynomial-time solution, including an exact rational optimal solution and value when feasible with finite optimum.
Its hypotheses are verified:
The displayed dense-encoding bound is a valid polynomial upper bound under the usual LP representation with nonnegativity specified as variable bounds. Enumerating triples and writing coefficients also requires only polynomial time.
Consequently, the exact-optimization conclusion follows from the cited theorem. Exact comparison with the rational budget \(K\) is likewise polynomial-time.
The output fully addresses the divisible-mass problem. Its observation that the discrete hardness result does not transfer is justified: the present task is exactly the rational LP analyzed above.
No additional clarification or repair is needed.
⟨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.