Answer: Exactly solvable in polynomial time; admits a multiplicative \(1\)-approximation in \((m+\tau+s+L)^{O(1)}\) bit operations for \(m=2\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateAssuming W[1] ̸= FPT, there exist (continuous) willingness functions, f j(·)’s, such that the EBEU problem does not admit any g(k)- approximation algorithm that runs in FPT time parameter- ized by k for any computable function g, even if m = 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given two candidates \(c_1,c_2\), rational masses \(\mu_t\) over voter types, a target \(c_2\), recipient mass \(\kappa\), per-capita budget \(B\), and explicit rational piecewise-linear willingness functions \(f_t\), is there a feasible payment schedule that makes \(c_2\) win in the deterministic nonatomic electorate?
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Masses sum to \(1\).
There are \(m=2\) candidates under plurality. Each type specifies a strict preference and an explicitly encoded continuous piecewise-linear function \(f_t:[0,\infty)\to[0,1]\), with rational breakpoints and affine coefficients, including its final ray; monotonicity is not required.
Let \(T_1\) be the types initially supporting \(c_1\), and let \(\beta\) be the initial mass supporting the target \(c_2\). Assume \(\beta<1/2\). Ties favor \(c_1\).
The inputs also include binary rationals \(B>0\) and \(0<\kappa\le1-\beta\), representing budget per unit of total society mass and exact recipient mass.
A payment schedule consists of finite nonnegative Borel measures \(\nu_t\) on \([0,\infty)\), for \(t\in T_1\), satisfying \(\nu_t([0,\infty))\le\mu_t\), \(\sum_{t\in T_1}\nu_t([0,\infty))=\kappa\), and \(\sum_{t\in T_1}\int x\,d\nu_t(x)\le B\). Thus portions of one type may receive different payments, including zero.
A recipient portion of mass \(z\) paid \(x\) transfers exactly \(zf_t(x)\) votes from \(c_1\) to \(c_2\); unselected mass retains its original vote. Write \(S=\sum_{t\in T_1}\int f_t(x)\,d\nu_t(x)\). The deterministic winning objective is \(W=1\) when \(\beta+S>1/2\), and \(W=0\) otherwise.
Let \(s\) count all encoded linear pieces and \(L\) be the total input bit length; state running times in \(m,\tau,s,L\), with \(B,\kappa\) included in \(L\).
Does maximizing \(W\) admit a multiplicative \(a\)-approximation for some fixed finite \(a\ge1\) in time polynomial in \(m,\tau,s,L\), or is obtaining such an approximation NP-hard?
For finite electorates, maximizing the target's winning probability admits no multiplicative \(g(k)\)-approximation in FPT time parameterized by recipient count \(k\), for any computable \(g\), assuming \(\mathrm{FPT}\ne\mathrm{W}[1]\), even with two candidates and continuous willingness functions. [Source](https://www.ijcai.org/proceedings/2019/0023.pdf)
No result settling this precise deterministic nonatomic model was located.
1. Result
The problem is exactly solvable in polynomial time. In particular, it admits a multiplicative \(1\)-approximation in \((m+\tau+s+L)^{O(1)}\) bit operations, with \(m=2\).
The essential property is the permission to split a type’s mass among different payments. This gives an exact finite linear programming formulation, even when willingness functions are nonmonotone.
2. Reduction to finitely many payment amounts
Fix a type \(t\in T_1\). Write its distinct piece endpoints as
\(\displaystyle 0=q_{t,0}<q_{t,1}<\cdots<q_{t,r_t},\)
where the final ray starts at \(q_{t,r_t}\). If the function has only a final ray, take \(r_t=0\). Define \(v_{t,j}=f_t(q_{t,j})\).
First, the final ray is constant. Indeed, if its affine expression is \(ax+b\), then \(a>0\) eventually violates \(f_t(x)\le 1\), and \(a<0\) eventually violates \(f_t(x)\ge 0\). Thus \(a=0\). Consequently, replacing any payment \(x\ge q_{t,r_t}\) by \(q_{t,r_t}\) preserves transferred votes and weakly decreases cost.
Next, suppose \(q_{t,j}\le x<q_{t,j+1}\). Define
\(\displaystyle \lambda=\frac{q_{t,j+1}-x}{q_{t,j+1}-q_{t,j}}.\)
Then \(0\le\lambda\le1\) and
\(\displaystyle x=\lambda q_{t,j}+(1-\lambda)q_{t,j+1}.\)
Because \(f_t\) is affine on this interval and continuous at its endpoints,
\(\displaystyle f_t(x)=\lambda v_{t,j}+(1-\lambda)v_{t,j+1}.\)
Therefore, a recipient portion of mass \(z\) paid \(x\) can instead be split into portions of masses \(z\lambda\) and \(z(1-\lambda)\), paid the two endpoints. Recipient mass, cost, and transferred votes are all preserved.
This replacement also applies rigorously to arbitrary Borel measures. For each \(x\), let \(w_{t,j}(x)\) be the endpoint weights just described: on a bounded interval, only its two endpoint weights are nonzero; on the final ray, the last endpoint has weight one. These are nonnegative Borel functions satisfying
\(\displaystyle \sum_{j=0}^{r_t}w_{t,j}(x)=1,\)
\(\displaystyle \sum_{j=0}^{r_t}q_{t,j}w_{t,j}(x)\le x,\)
\(\displaystyle \sum_{j=0}^{r_t}v_{t,j}w_{t,j}(x)=f_t(x).\)
Given a feasible measure \(\nu_t\), set
\(\displaystyle y_{t,j}=\int w_{t,j}(x)\,d\nu_t(x),\qquad \widehat{\nu}_t=\sum_{j=0}^{r_t}y_{t,j}\delta_{q_{t,j}},\)
where \(\delta_q\) denotes unit point mass at \(q\). Integrating the three identities or inequalities proves that \(\widehat{\nu}_t\) has the same recipient mass and transferred votes as \(\nu_t\), and no greater cost.
Thus every feasible schedule can be replaced by a schedule supported on the encoded endpoints, preserving its winning status. No monotonicity assumption was used.
3. The exact linear program
Introduce a nonnegative variable \(y_{t,j}\) for the recipient mass of type \(t\) paid \(q_{t,j}\). Solve the following rational linear program:
\(\displaystyle \text{maximize }\quad \sum_{t\in T_1}\sum_{j=0}^{r_t}v_{t,j}y_{t,j},\)
subject to
\(\displaystyle \sum_{j=0}^{r_t}y_{t,j}\le\mu_t\qquad(t\in T_1),\)
\(\displaystyle \sum_{t\in T_1}\sum_{j=0}^{r_t}y_{t,j}=\kappa,\)
\(\displaystyle \sum_{t\in T_1}\sum_{j=0}^{r_t}q_{t,j}y_{t,j}\le B,\)
\(\displaystyle y_{t,j}\ge0\qquad(t\in T_1,\ 0\le j\le r_t).\)
Call its optimal value \(V\).
Every feasible vector defines an admissible schedule by taking \(\nu_t=\sum_jy_{t,j}\delta_{q_{t,j}}\); its transferred vote mass equals the objective value. Conversely, Section 2 transforms every admissible schedule into a feasible vector with exactly the same transferred vote mass. Hence the linear program captures the original optimization of \(S\) exactly.
The feasible set is nonempty. Since the two candidates exhaust the initial support, \(\sum_{t\in T_1}\mu_t=1-\beta\). Set
\(\displaystyle y_{t,0}=\frac{\kappa}{1-\beta}\mu_t,\qquad y_{t,j}=0\quad(j>0).\)
The assumption \(\kappa\le1-\beta\) ensures the type capacity constraints, the total recipient mass is \(\kappa\), and the cost is zero.
The feasible set is closed and bounded: each coordinate satisfies \(0\le y_{t,j}\le\mu_t\). It is therefore compact, so its continuous linear objective attains a maximum. In particular, \(V\) is attained by an admissible schedule.
4. Bit complexity and the strict winning threshold
Let \(p_t\) be the number of encoded pieces of \(f_t\), including its final ray. After removing duplicate endpoints, \(r_t+1\le p_t\). Thus the number of variables is
\(\displaystyle N=\sum_{t\in T_1}(r_t+1)\le s.\)
Apart from nonnegativity constraints, there are at most \(\tau\) type capacity inequalities, one recipient mass equality, and one budget inequality.
All coefficients are rational. Each \(v_{t,j}\) is obtained by evaluating an encoded rational affine expression at an encoded rational endpoint, so its bit length is \(O(L)\). A dense encoding of the entire linear program has length \(O((s+\tau)^2L)\).
We use the standard rational linear programming theorem: a linear program with binary rational data can be solved exactly, including producing a rational optimal solution when a finite optimum exists, in time polynomial in its encoding length. Exact recovery, rather than merely approximate optimization, is explicitly discussed in [Vishnoi’s linear programming notes](https://nisheethvishnoi.wordpress.com/wp-content/uploads/2018/05/lecture71.pdf). Its hypotheses hold here: the data are rational, the feasible set is nonempty, and the optimum is finite and attained.
Consequently, an optimal vector \(y^*\), its value \(V\), and the associated finite schedule can be computed in \((m+\tau+s+L)^{O(1)}\) bit operations for \(m=2\). Their encodings have polynomial length. This bound includes the binary encodings of \(B\) and \(\kappa\).
Compare \(V\) and \(\frac12-\beta\) using exact rational arithmetic:
Equality is therefore handled correctly under the specified tie rule.
5. Approximation consequence and relation to the cited result
The algorithm returns an optimal schedule for \(W\). It consequently satisfies \(W_{\mathrm{alg}}\ge W_{\mathrm{opt}}/a\) for every fixed finite \(a\ge1\), including \(a=1\).
The cited finite-electorate hardness theorem concerns selecting indivisible voters and maximizing a stochastic winning probability. [Its Theorem 1](https://www.ijcai.org/proceedings/2019/0023.pdf) does not establish hardness for this deterministic nonatomic model. Here, divisible recipient mass and affine interpolation yield the exact linear program proved above.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The endpoint reduction applies to arbitrary admissible Borel measures, the resulting rational linear program has polynomial encoding length, and exact optimization handles the strict winning threshold. I found no major or minor issues.
The argument uses both bounds in the specified codomain \( [0,1] \). A positive affine slope would eventually exceed \(1\), and a negative slope would eventually fall below \(0\). Therefore its slope must be zero.
Replacing a payment on the final ray by the ray’s starting point preserves transferred votes and does not increase cost. This also covers the case \(r_t=0\), where the entire function is constant.
Distinct consecutive endpoints satisfy \(q_{t,j+1}>q_{t,j}\), so the denominator defining \(\lambda\) is positive. For every payment in the indicated interval, the stated weights are nonnegative and sum to one.
Both identities—for the payment and for the willingness value—follow from affine interpolation. Continuity ensures that the encoded endpoint values agree with the adjoining affine pieces. Splitting a recipient portion according to these weights consequently preserves recipient mass, cost, and transferred votes. No monotonicity assumption enters this argument.
The endpoint weights are Borel measurable because their definitions are affine on finitely many Borel intervals and constant on the final ray. At shared endpoints, the interpolation descriptions assign unit weight to that endpoint, so there is no conflicting assignment.
Each weight lies in \([0,1]\), and each input measure is finite. Thus every \(y_{t,j}\) is well-defined and finite. Integrating the pointwise identities preserves total recipient mass and transferred votes. Integrating the pointwise cost inequality gives no greater cost; the original cost integral is finite by feasibility.
Therefore the reduction genuinely applies to all schedules allowed by USER_TASK, including schedules with infinitely many payment amounts.
Every feasible LP vector defines finite nonnegative atomic Borel measures satisfying the type capacities, exact recipient mass, and budget constraint. Its objective equals the resulting transferred vote mass.
Conversely, the measure reduction sends every admissible schedule to a feasible LP vector with the same transferred vote mass. Both directions are established, so the formulation is exact.
The displayed zero-payment vector proves nonemptiness: \(1-\beta>0\), the multiplier \(\kappa/(1-\beta)\) lies in \((0,1]\), its recipient masses sum to \(\kappa\), and its cost is zero. The argument correctly permits selected mass to receive zero payment.
The feasible set is closed and bounded in finite-dimensional space. The continuous objective therefore attains its maximum. This attainment is essential to the later strict-threshold argument and is established explicitly.
For each type, a partition with \(p_t\) pieces including its final ray has at most \(p_t\) relevant endpoints, including zero. Hence \(N\le s\). The stated constraint count is correct.
Evaluating a rational affine expression at a rational breakpoint requires only a constant number of rational arithmetic operations, so each resulting coefficient has bit length \(O(L)\). The claimed dense LP encoding bound \(O((s+\tau)^2L)\) is a valid upper bound. Computing \(\beta\) from the encoded masses also has polynomial bit complexity.
The invoked theorem—polynomial-time exact optimization of rational linear programs, with a rational optimal solution when a finite optimum exists—is applicable. Rational data, feasibility, boundedness, and attainment have all been verified. Equalities and a possibly lower-dimensional feasible set are permitted by this general theorem. The cited notes explicitly discuss exact recovery and polynomial-size rational optimal solutions. [Vishnoi’s linear programming notes](https://nisheethvishnoi.wordpress.com/wp-content/uploads/2018/05/lecture71.pdf)
Consequently, the claimed polynomial bit-operation bound and polynomial-length output schedule follow. The budget and recipient mass are included in the input encoding.
If \(V>\frac12-\beta\), an attained LP optimum supplies an admissible winning schedule. If \(V\le\frac12-\beta\), equivalence implies that every admissible schedule fails the strict winning condition.
Exact rational comparison distinguishes equality correctly. There is no reliance on numerical tolerance or on an unattained supremum.
An optimal schedule for transferred votes maximizes the binary winning objective by the preceding threshold analysis. When the optimal winning value is \(1\), the algorithm returns \(1\); when it is \(0\), any feasible output is optimal. Thus the claimed multiplicative \(1\)-approximation follows.
The cited finite-electorate theorem concerns the stochastic bribery model with individual voters and states the indicated parameterized inapproximability. The prover correctly avoids applying it to the deterministic divisible-mass model. [IJCAI 2019, Theorem 1](https://www.ijcai.org/proceedings/2019/0023.pdf)
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.