Answer: Polynomial-time solvable for \(m=2\), including exact computation of the optimal value and an explicit optimal scheme with at most \(D+1\) rational share vectors per state.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLP (1) computes an optimal solution of PRIVATE-DBE in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite state set Θ with rational prior π, districts \(d=1,…,D\), and rational masses μ_dt over supported voter types with utility differences \(u_{dt}(θ)\), find an optimal private signaling scheme. Represent the scheme, conditional on each state θ, by a probability law Λ_θ over recommendation shares \(x_{dt}∈[0,1]\), where \(x_{dt}\) is the fraction of type \(t\)'s mass in district \(d\) recommended \(c_0\). With \(q_{dtθ}=ᵓ_{Λ_θ}[x_{dt}]\), require \(∑_θ π_θ q_{dtθ}u_{dt}(θ)≥0\) and \(∑_θ π_θ(1-q_{dtθ})u_{dt}(θ)≤0\) for every type. Maximize the expected probability that \(c_0\) wins: in each realized allocation, district \(d\)'s \(c_0\) vote share is \(∑_t μ_{dt}x_{dt}\), and \(c_0\) wins the election if at least \(\lceil D/2\rceil\) districts have a share of at least \(1/2\).
There are \(m=2\) candidates \(c_0,c_1\), \(D\ge1\) districts, and a nonempty finite state set \(\Theta\) with binary-rational prior \(\pi_\theta>0\), \(\sum_\theta\pi_\theta=1\).
A society is given by its support: the list of its \(\tau\) types with positive binary-rational masses; \(\tau\) is the support size, not the number of possible types. A type includes its district. Write \(T_d\ne\varnothing\) for district \(d\)'s supported types, with \(\mu_{dt}>0\) and \(\sum_{t\in T_d}\mu_{dt}=1\).
Each type has binary-rational utility differences \(u_{dt}(\theta)\in[-1,1]\) between voting for \(c_0\) and \(c_1\); utility depends only on its own vote and the state. Let \(L\) be the total input bit length.
The sender commits to a private direct signaling scheme: conditional on \(\theta\), a Borel probability law \(\Lambda_\theta\) on \([0,1]^\tau\) selects shares \(x_{dt}\) of each type recommended \(c_0\); the remaining shares are recommended \(c_1\). Each voter observes only its own recommendation, with marginal probability \(q_{dt\theta}=\mathbb E_{\Lambda_\theta}[x_{dt}]\); arbitrary correlation is allowed.
Persuasiveness requires \(\sum_\theta\pi_\theta q_{dt\theta}u_{dt}(\theta)\ge0\) and \(\sum_\theta\pi_\theta(1-q_{dt\theta})u_{dt}(\theta)\le0\) for every supported type; indifferent voters follow their recommendations.
Define \(W(x)=\mathbf1\!\left\{\left|\left\{d:\sum_{t\in T_d}\mu_{dt}x_{dt}\ge\tfrac12\right\}\right|\ge\lceil D/2\rceil\right\}\). Thus electoral ties favor \(c_0\). The objective is to maximize \(\sum_\theta\pi_\theta\mathbb E_{\Lambda_\theta}[W(x)]\).
Is this exact optimal private-signaling problem solvable in time polynomial in \(m,\tau,D,|\Theta|,L\), or is it NP-hard?
For a finite explicitly listed electorate with the same two-stage majority rule, optimal private signaling is computable in polynomial time ([Castiglioni and Gatti](https://arxiv.org/pdf/2012.05002)).
No result settling this exact continuous problem was located in the literature search.
The exact optimal private-signaling problem is solvable in polynomial time for \(m=2\). Moreover, an optimal scheme can be output explicitly, with at most \(D+1\) rational share vectors per state.
The proof uses a polynomial-size rational linear program and an explicit reconstruction of a signaling scheme. It directly handles the continuous model; the cited [finite-electorate result](https://arxiv.org/pdf/2012.05002) is not needed for the argument.
Let \(k\) be an integer with \(1\le k\le D\).
Lemma. Suppose \(y\in[0,1]^D\) and \(\sum_{d=1}^D y_d=k\). There is a probability distribution on subsets \(A\subseteq\{1,\ldots,D\}\) such that
\(\displaystyle |A|=k\quad\text{always},\qquad \Pr(d\in A)=y_d\quad\text{for every }d.\)
If \(y\) is rational, such a distribution can be computed exactly in polynomial time and represented using at most \(D\) subsets with rational probabilities.
Proof. Put \(s_0=0\) and \(s_d=\sum_{i=1}^d y_i\). The half-open intervals
\(\displaystyle I_d=[s_{d-1},s_d)\)
partition \([0,k)\). Draw \(U\) uniformly from \([0,1)\), and select district \(d\) exactly when \(I_d\) contains one of
\(\displaystyle U,\ U+1,\ \ldots,\ U+k-1.\)
These are exactly \(k\) points in \([0,k)\). Each belongs to exactly one interval. Because every interval has length at most \(1\), no interval contains two of these points. Thus exactly \(k\) distinct districts are selected.
For a fixed district \(d\), the events \(U+j\in I_d\), for \(j=0,\ldots,k-1\), are disjoint. Their probabilities sum to
\(\displaystyle \sum_{j=0}^{k-1}\operatorname{length}\bigl(I_d\cap[j,j+1)\bigr)=\operatorname{length}(I_d)=y_d.\)
This proves the required marginal probabilities.
For rational \(y\), the selected subset changes only at fractional parts of the cumulative sums \(s_d\). Partition \([0,1)\) at those breakpoints and choose a midpoint in each interval. Assign the resulting subset probability equal to that interval’s length. The finitely many endpoints have probability zero.
Since \(s_0=0\) and \(s_D=k\) have fractional part zero, there are at most \(D-1\) internal breakpoints, giving at most \(D\) subsets. All operations are rational additions, comparisons, and divisions, with polynomial bit complexity. \(\square\)
Set \(k=\lceil D/2\rceil\). For every state \(\theta\), introduce variables
\(\displaystyle w_\theta,\qquad p_{d\theta}\ (d=1,\ldots,D),\qquad q_{dt\theta},\,a_{dt\theta},\,z_{dt\theta}\ (t\in T_d).\)
Their intended meanings are:
Maximize
\(\displaystyle \sum_{\theta\in\Theta}\pi_\theta w_\theta\)
subject to the following constraints.
For every state \(\theta\),
\(\displaystyle 0\le w_\theta\le1,\qquad 0\le q_{dt\theta}\le1;\)
\(\displaystyle 0\le p_{d\theta}\le w_\theta,\qquad \sum_{d=1}^D p_{d\theta}=k w_\theta.\)
For every district \(d\), type \(t\in T_d\), and state \(\theta\),
\(\displaystyle 0\le z_{dt\theta}\le p_{d\theta};\)
\(\displaystyle \sum_{t\in T_d}\mu_{dt}z_{dt\theta}\ge \frac12p_{d\theta};\)
\(\displaystyle 0\le a_{dt\theta}-z_{dt\theta}\le w_\theta-p_{d\theta};\)
\(\displaystyle 0\le q_{dt\theta}-a_{dt\theta}\le1-w_\theta.\)
Finally, impose both persuasiveness inequalities for every supported type:
\(\displaystyle \sum_{\theta\in\Theta}\pi_\theta q_{dt\theta}u_{dt}(\theta)\ge0,\)
\(\displaystyle \sum_{\theta\in\Theta}\pi_\theta(1-q_{dt\theta})u_{dt}(\theta)\le0.\)
Call this linear program \(\mathcal L\). Its exactness requires proving both directions below.
Fix an arbitrary persuasive scheme \((\Lambda_\theta)_{\theta\in\Theta}\).
For each share vector \(x\) with \(W(x)=1\), select the first \(k\) winning districts in the ordering \(1,\ldots,D\). Denote this subset by \(A(x)\). Set \(A(x)=\varnothing\) when \(W(x)=0\).
This selection is Borel measurable: each district’s winning condition is a closed linear inequality, and the selection uses finitely many Boolean combinations of those conditions.
For each state, define
\(\displaystyle w_\theta=\mathbb E_{\Lambda_\theta}[W(x)],\qquad q_{dt\theta}=\mathbb E_{\Lambda_\theta}[x_{dt}],\)
\(\displaystyle p_{d\theta}=\mathbb E_{\Lambda_\theta}[\mathbf1_{\{d\in A(x)\}}],\)
\(\displaystyle a_{dt\theta}=\mathbb E_{\Lambda_\theta}[W(x)x_{dt}],\qquad z_{dt\theta}=\mathbb E_{\Lambda_\theta}[\mathbf1_{\{d\in A(x)\}}x_{dt}].\)
Exactly \(k\) districts are selected whenever \(W(x)=1\), so
\(\displaystyle \sum_d p_{d\theta}=k w_\theta.\)
Since a selected district is winning,
\(\displaystyle \mathbf1_{\{d\in A(x)\}}\sum_{t\in T_d}\mu_{dt}x_{dt}\ge\frac12\mathbf1_{\{d\in A(x)\}}.\)
Taking expectations gives the district-threshold constraint.
The remaining bounds follow from \(0\le x_{dt}\le1\). In particular,
\(\displaystyle a_{dt\theta}-z_{dt\theta}=\mathbb E_{\Lambda_\theta}\bigl[(W(x)-\mathbf1_{\{d\in A(x)\}})x_{dt}\bigr]\in[0,w_\theta-p_{d\theta}],\)
and
\(\displaystyle q_{dt\theta}-a_{dt\theta}=\mathbb E_{\Lambda_\theta}[(1-W(x))x_{dt}]\in[0,1-w_\theta].\)
Persuasiveness holds because the variables \(q_{dt\theta}\) are the scheme’s actual marginals.
Thus the scheme produces a feasible LP point with exactly the same objective value. Consequently, every achievable victory probability is at most the optimum of \(\mathcal L\).
Fix a feasible LP point. Construct the distribution separately in each state, suppressing \(\theta\) temporarily.
First suppose \(w>0\). Define \(y_d=p_d/w\). The LP constraints imply
\(\displaystyle 0\le y_d\le1,\qquad \sum_d y_d=k.\)
Apply the lemma to obtain a random subset \(A\) of exactly \(k\) districts with \(\Pr(d\in A)=p_d/w\).
For each such subset, define a deterministic share vector \(x^A\) district by district:
\(\displaystyle x^A_{dt}=\frac{z_{dt}}{p_d}\quad\text{if }d\in A,\)
and
\(\displaystyle x^A_{dt}=\frac{a_{dt}-z_{dt}}{w-p_d}\quad\text{if }d\notin A.\)
These expressions are used only when their denominators are positive. If \(p_d=0\), district \(d\) is never selected; if \(p_d=w\), it is always selected. Hence a zero denominator occurs only in an unused branch.
The LP bounds show that every used coordinate lies in \([0,1]\). Every selected district satisfies
\(\displaystyle \sum_{t\in T_d}\mu_{dt}x^A_{dt}=\frac{\sum_{t\in T_d}\mu_{dt}z_{dt}}{p_d}\ge\frac12.\)
There are exactly \(k\) selected districts, so \(W(x^A)=1\) for every realization.
For \(0<p_d<w\), the expected share in this component is
\(\displaystyle \mathbb E[x^A_{dt}]=\frac{p_d}{w}\frac{z_{dt}}{p_d}+\frac{w-p_d}{w}\frac{a_{dt}-z_{dt}}{w-p_d}=\frac{a_{dt}}{w}.\)
The boundary cases give the same result: when \(p_d=0\), the constraints force \(z_{dt}=0\); when \(p_d=w\), they force \(a_{dt}=z_{dt}\).
If \(w<1\), also define the residual vector
\(\displaystyle r_{dt}=\frac{q_{dt}-a_{dt}}{1-w}.\)
The residual constraints ensure \(r\in[0,1]^\tau\). Assign probability \(w\) to the guaranteed-victory component and probability \(1-w\) to \(r\). The resulting marginal is
\(\displaystyle w\frac{a_{dt}}w+(1-w)r_{dt}=q_{dt}.\)
When \(w=1\), the constraints give \(q_{dt}=a_{dt}\), and only the guaranteed-victory component is used. When \(w=0\), they force \(p_d=z_{dt}=a_{dt}=0\), and the point mass at \(q\) supplies the required marginals.
Performing this construction in every state yields Borel probability laws with precisely the LP marginals. Therefore both persuasiveness inequalities hold. Their victory probability is at least
\(\displaystyle \sum_\theta\pi_\theta w_\theta.\)
The residual vector may itself win; the construction only requires a lower bound on victory probability.
The LP is nonempty. For example, take \(w_\theta=p_{d\theta}=a_{dt\theta}=z_{dt\theta}=0\), and choose \(q_{dt\theta}=1\) when \(u_{dt}(\theta)\ge0\), and \(q_{dt\theta}=0\) otherwise. Both obedience inequalities then hold term by term.
Its feasible region is closed and bounded: the displayed constraints bound every variable between zero and one. Thus it has an attained optimum, say \(V_{\mathcal L}\).
Section 3 shows that every persuasive scheme has value at most \(V_{\mathcal L}\). Section 4 reconstructs from an optimal LP point a persuasive scheme with value at least \(V_{\mathcal L}\). Therefore that scheme has value exactly \(V_{\mathcal L}\), and the original continuous optimization problem has an attained optimum equal to the LP optimum.
There are
\(\displaystyle |\Theta|(3\tau+D+1)\)
variables and \(O(|\Theta|(\tau+D)+\tau)\) constraints. All coefficients are rational with total encoding length polynomial in the input length \(L\). In particular, forming the products \(\pi_\theta u_{dt}(\theta)\) requires only polynomial bit complexity.
The standard rational linear-programming theorem computes an exact optimal rational solution in time polynomial in the number of variables, constraints, and coefficient encoding length. Its hypotheses hold here: the LP is explicitly given, rational, feasible, and bounded.
For such a rational solution, the lemma produces at most \(D\) subsets per state. The reconstruction adds at most one residual vector, so each state’s law has at most \(D+1\) atoms. All probabilities and coordinates are rational and computable with polynomial bit complexity.
Electoral ties are handled exactly by the weak district inequality. Equality at the threshold already certifies a district victory, so the proof requires no approximation or limiting argument.
⟨structured verdict parsed — rendered above⟩
The proof resolves the stated continuous problem. Both directions of the LP equivalence are valid, the reconstruction handles all boundary cases, and the claimed polynomial running time and support bound follow. I found no major or minor issues.
The lemma is correct for every integer \(1\le k\le D\), including \(k=D\).
Thus the construction selects exactly \(k\) distinct districts for every \(U\in[0,1)\).
For each district, the events indexed by \(j\) are disjoint, and their probabilities equal the lengths of the corresponding interval intersections. Their sum is \(y_d\), establishing the asserted marginal.
The finite rational implementation is also valid. Selection changes only at fractional parts of cumulative sums. There are at most \(D-1\) distinct internal breakpoints because both endpoint cumulative sums have fractional part zero. Consequently there are at most \(D\) positive-length intervals and hence at most \(D\) subsets in the resulting distribution. Using midpoints and interval lengths involves rational operations with polynomial bit complexity.
All displayed constraints are linear with rational coefficients. The variable count \( |\Theta|(3\tau+D+1) \) is correct.
The bounds also control the variables that lack separate upper bounds:
The district-threshold constraint is naturally indexed by district and state. Its placement under a type-indexed introduction could produce repeated identical rows, but this does not change feasibility or the asserted asymptotic constraint count.
Both obedience inequalities from the task appear unchanged. No additional restriction on correlation is imposed.
The selection \(A(x)\) is Borel measurable as asserted: district victory is specified by a closed linear inequality, and selecting the first \(k\) winning districts requires only finitely many Boolean combinations of those conditions.
The expectation definitions are well-defined because all integrands are bounded and measurable.
Every constraint follows from the definitions:
The LP marginals equal the original scheme’s marginals, so persuasiveness is preserved exactly. The objective is also preserved exactly. This establishes the required upper bound for every admissible Borel signaling scheme.
For \(w>0\), the normalized district marginals \(y_d=p_d/w\) satisfy every hypothesis of the selection lemma.
The reconstruction is valid:
The division boundary cases are handled correctly. When \(p_d=0\), selection has probability zero and \(z_{dt}=0\). When \(p_d=w\), nonselection has probability zero and \(a_{dt}=z_{dt}\). Thus no branch used with positive probability has a zero denominator.
For \(0<p_d<w\), the stated expectation calculation is correct and gives \(a_{dt}/w\). The two boundary cases give the same expectation.
When \(w<1\), the residual bounds ensure that \(r\) is an admissible share vector. Mixing it with the guaranteed-victory component gives exactly the required marginal \(q_{dt}\). The separate treatments of \(w=0\) and \(w=1\) are correct.
The resulting finite distributions are Borel probability laws. Their marginals satisfy both obedience inequalities, and their objective is at least the LP objective. Allowing the residual vector to win creates no gap: this direction requires a lower bound, exactly as the prover states.
The proposed feasible point is valid. With the four component variables zero, all component constraints hold. For the specified \(q\):
Zero utility differences cause no difficulty.
The feasible region is closed and bounded in finite-dimensional space and is nonempty. Its linear objective therefore attains its maximum.
The two established directions yield exact equality of optimal values. In particular, reconstructing an optimal LP point gives a scheme with value at least the LP optimum, while the scheme-to-LP direction bounds that same scheme’s value above by the LP optimum. Hence the reconstructed scheme is optimal and the continuous optimum is attained.
The LP has the claimed polynomial numbers of variables and constraints. Its coefficients, including products of priors and utility differences, have polynomial total binary encoding length.
The rational LP theorem is stated with the relevant conclusion: exact computation of an optimal rational solution in polynomial time in the explicit LP dimensions and coefficient encoding length. The write-up verifies rationality, explicit representation, feasibility, and boundedness, so its application is justified.
The subsequent reconstruction uses polynomially many rational arithmetic operations. Cumulative sums, breakpoint computations, and divisions preserve polynomial bit lengths. The district-selection component uses at most \(D\) atoms, and the residual component contributes at most one, establishing the claimed \(D+1\) bound per state.
The argument applies to support size \(\tau\), without expanding supported types into a finite electorate. It covers \(D=1\), singleton state sets, singleton district supports, zero utility differences, and all reconstruction boundary cases.
The weak district inequalities and the choice \(k=\lceil D/2\rceil\) match both tie conventions in the task. No approximation or limiting argument is used.
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.