Answer: The general sparse rational-mass decision problem is NP-complete, already for \(k=\lfloor t/2\rfloor+2\). For \(k=\lfloor t/2\rfloor+1\), a deterministic polynomial-time exact-arithmetic algorithm outputs a policy \(p\) with \(B_\mu(p)\ge 0\) and \(d_H(p,q) \le \lfloor (t-1)/2 \rfloor\).
Theorem 19 — class: algorithmic
There is a polynomial-time deterministic algorithm that computes a non-losing policy 𝑝∈𝐵𝑚. If Δ > 0, then the com- puted policy is winning. PRoof. We only show the “non-losing” part of the assertion.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(t\) binary issues, a rational distribution \(\mu\) over ballot types \(v\in\{0,1\}^t\), and \(k\), decide whether there is a policy \(p\in\{0,1\}^t\) with \(d_H(p,q)\le t-k\) and \(B_\mu(p)\ge0\), where \(q\) is coordinatewise issue-wise majority and \(B_\mu\) is mass of supporters minus mass of opponents; compute such a policy for \(k=\lfloor t/2\rfloor+1\).
A rational society is given by a sparse list of pairs \((v,\mu(v))\), where \(v\in\{0,1\}^t\), \(\mu(v)\ge0\) is rational, and the masses sum to 1. Let \(q_j=1\) iff \(\mu(\{v:v_j=1\})\ge1/2\), and otherwise let \(q_j=0\). For a policy \(p\), set \(B_\mu(p)=\mu(\{v:d_H(v,p)<t/2\})-\mu(\{v:d_H(v,p)>t/2\})\).
Target. Is deciding whether there is a \(p\in\{0,1\}^t\) with \(B_\mu(p)\ge0\) and at least \(k\) agreements with \(q\) polynomial-time solvable, or NP-hard?
For \(k=\lfloor t/2\rfloor+1\), is there a polynomial-time algorithm that outputs such a \(p\) (equivalently, with \(d_H(p,q)\le\lfloor(t-1)/2\rfloor\))?
For finite unweighted profiles, a deterministic polynomial-time algorithm outputs a non-losing policy within distance \(\lfloor(t-1)/2\rfloor\) of issue-wise majority. For the related finite-profile decision problem, requiring at least \(\lfloor t/2\rfloor+2\) agreements is NP-hard.
Let the rational society be represented by a binary-encoded sparse list of $m$ ballot types and their rational masses.
The decision problem is NP-complete, already under the restriction
$$ k=\left\lfloor\frac t2\right\rfloor+2. $$
In contrast, for
$$ k=\left\lfloor\frac t2\right\rfloor+1, $$
there is a deterministic polynomial-time algorithm that outputs a policy $p$ satisfying
$$ B_\mu(p)\ge 0 \qquad\text{and}\qquad d_H(p,q)\le \left\lfloor\frac{t-1}{2}\right\rfloor. $$
Thus the finite-profile tractability-versus-hardness boundary survives sparse rational weights.
Write the listed masses as
$$ \mu(v_i)=\frac{a_i}{b_i},\qquad i=1,\ldots,m, $$
with positive integer denominators. Let
$$ W=\prod_{i=1}^m b_i, \qquad w_i=a_i\frac{W}{b_i}. $$
Then every $w_i$ is an integer and, because the masses sum to one,
$$ \sum_{i=1}^m w_i=W. $$
Although the numerical value of $W$ can be exponential, its binary length is at most the sum of the binary lengths of the denominators. Hence $W$ and all $w_i$ can be computed and manipulated in polynomial time.
For every policy $p$,
$$ B_\mu(p)=\frac1W\sum_{i=1}^m w_i\operatorname{sgn}\bigl(t-2d_H(v_i,p)\bigr), $$
where $\operatorname{sgn}(0)=0$. Consequently, the sign of $B_\mu(p)$ can be checked using exact integer arithmetic.
A certificate is a policy $p\in\{0,1\}^t$.
Using the integer weights above, one can compute:
$$ \sum_{i=1}^m w_i\operatorname{sgn}\bigl(t-2d_H(v_i,p)\bigr). $$
The certificate is accepted exactly when the agreement count is at least $k$ and the last integer is nonnegative. This takes polynomial time, so the problem belongs to NP.
Use the stated NP-hard finite-profile problem with threshold
$$ k=\left\lfloor\frac t2\right\rfloor+2. $$
Let its unweighted profile contain $n$ voters. For every distinct ballot $v$, let $c_v$ be its multiplicity and construct the rational society
$$ \mu(v)=\frac{c_v}{n}. $$
This construction is polynomial-time: there are at most $n$ distinct ballots, and every mass has polynomial binary length.
For every issue $j$,
$$ \mu(\{v:v_j=1\}) = \frac{\#\{\text{voters with }v_j=1\}}{n}. $$
Hence the rational society and the original profile have the same issue-wise majority policy, including the prescribed convention that a tie selects $1$.
Moreover, for every policy $p$,
$$ B_\mu(p) = \frac{ \#\{\text{voters supporting }p\} - \#\{\text{voters opposing }p\} }{n}. $$
Thus $B_\mu(p)\ge0$ exactly when $p$ is non-losing in the original profile. The agreement constraint is unchanged. The reduction therefore preserves yes-instances and no-instances.
It follows that the sparse rational decision problem is NP-hard at the displayed threshold. Together with membership in NP, it is NP-complete.
For the constructive result, first transform the instance so that the majority policy is the all-ones policy.
For each coordinate define
$$ \widetilde p_j= \begin{cases} p_j,&q_j=1,\\ 1-p_j,&q_j=0, \end{cases} \qquad \widetilde v_j= \begin{cases} v_j,&q_j=1,\\ 1-v_j,&q_j=0. \end{cases} $$
Applying the same coordinate flip to ballots and policies preserves all Hamming distances. Furthermore,
$$ |\widetilde p|=t-d_H(p,q). $$
In the transformed instance, the mass having value $1$ on every coordinate is at least $1/2$. Indeed, if $q_j=1$, this follows from its definition; if $q_j=0$, the original mass of zeros is strictly greater than $1/2$.
It therefore suffices to find a transformed policy with more than $t/2$ ones and nonnegative balance. We henceforth omit tildes and assume $q=1^t$.
For a ballot $v$, introduce its sign vector $u\in\{-1,1\}^t$ by
$$ u_j=2v_j-1. $$
Likewise, write a policy as $x\in\{-1,1\}^t$, where $x_j=2p_j-1$. Define
$$ \beta(x)=\sum_{j=1}^t x_j=2|p|-t. $$
The voter score for $p$ is
$$ u\mathbin{\cdot}x=t-2d_H(v,p). $$
Let
$$ H=\left\{x\in\{-1,1\}^t:\beta(x)>0\right\}, \qquad C_t=\binom{t-1}{\lfloor t/2\rfloor}. $$
For every $u\in\{-1,1\}^t$,
$$ \sum_{x\in H}\beta(x)\operatorname{sgn}(u\mathbin{\cdot}x) = C_t\sum_{j=1}^t u_j. $$
Set
$$ g(x)=\beta(x)\operatorname{sgn}(u\mathbin{\cdot}x). $$
Because $g(-x)=g(x)$ and $g(x)=0$ when $\beta(x)=0$,
$$ \sum_{x\in H}g(x)=\frac12\sum_{x\in\{-1,1\}^t}g(x). $$
Expanding $\beta(x)$ gives
$$ \frac12\sum_{j=1}^t \sum_x x_j\operatorname{sgn}(u\mathbin{\cdot}x). $$
Make the bijective substitution $y_i=u_ix_i$. Then $x_j=u_jy_j$ and $u\mathbin{\cdot}x=\sum_i y_i$. Hence the inner sum is
$$ u_j A_t, \qquad A_t=\sum_{y\in\{-1,1\}^t} y_j\operatorname{sgn}\left(\sum_{i=1}^t y_i\right). $$
Fixing all coordinates except $j$ and writing $S=\sum_{i\ne j}y_i$, the sum over $y_j\in\{-1,1\}$ is
$$ \operatorname{sgn}(S+1)-\operatorname{sgn}(S-1). $$
If $t$ is odd, $S$ is even, and this expression is nonzero only for $S=0$, where it equals $2$. Therefore
$$ A_t=2\binom{t-1}{(t-1)/2}=2C_t. $$
If $t$ is even, $S$ is odd, and the expression equals $1$ for each of $S=1$ and $S=-1$, and is zero otherwise. Therefore
$$ A_t= \binom{t-1}{t/2} + \binom{t-1}{t/2-1} =2C_t. $$
Substitution yields
$$ \sum_{x\in H}g(x) = \frac12\sum_{j=1}^t u_j(2C_t) = C_t\sum_{j=1}^t u_j. $$
This proves the lemma.
For each coordinate define its normalized majority margin
$$ \delta_j=\sum_{i=1}^m\mu(v_i)(2v_{i,j}-1). $$
Since the transformed majority policy is all ones, $\delta_j\ge0$. Let
$$ \Delta=\sum_{j=1}^t\delta_j\ge0. $$
Choose $p$ uniformly among policies in $H$. Applying the lemma to each ballot type and taking the mass-weighted sum gives
$$ \mathbb E_{p\in H}\left[(2|p|-t)B_\mu(p)\right] = \frac{C_t}{|H|}\Delta \ge0. $$
Let
$$ h=\left\lfloor\frac t2\right\rfloor+1. $$
Partitioning the expectation according to $|p|=k$ yields
$$ \mathbb E_{p\in H}\left[(2|p|-t)B_\mu(p)\right] = \sum_{k=h}^t \Pr(|p|=k)(2k-t)\, \mathbb E[B_\mu(p)\mid |p|=k]. $$
Every coefficient in this sum is positive. Consequently, at least one $k\in\{h,\ldots,t\}$ satisfies
$$ \mathbb E[B_\mu(p)\mid |p|=k]\ge0. $$
The remaining task is to compute these expectations without enumerating the exponentially many policies.
Fix:
The partial policy has a completion of cardinality $k$ exactly when $0\le\ell\le r$. The number of such completions is
$$ \binom r\ell. $$
For a type $v$, define its score on the fixed coordinates by
$$ c_v=\sum_{j\in D} \begin{cases} 1,&v_j=p^*_j,\\ -1,&v_j\ne p^*_j. \end{cases} $$
Among the remaining coordinates, let $A_v$ be the number on which $v_j=1$ and let $Z_v=r-A_v$.
Suppose that exactly $x$ of the $\ell$ newly selected one-coordinates lie among those $A_v$ coordinates. The number of such completions is
$$ \binom{A_v}{x}\binom{Z_v}{\ell-x}. $$
The number of matches on the remaining coordinates is $Z_v-\ell+2x$. Hence the total score is
$$ s_v(x) = c_v+2Z_v-2\ell+4x-r. $$
It follows that the numerator of the conditional expected balance is
$$ N(k,p^*)= \sum_{v}w_v \sum_{x=\max\{0,\ell-Z_v\}}^{\min\{A_v,\ell\}} \binom{A_v}{x} \binom{Z_v}{\ell-x} \operatorname{sgn}(s_v(x)), $$
and therefore
$$ \mathbb E[B_\mu(p)\mid |p|=k,\ p\text{ refines }p^*] = \frac{N(k,p^*)}{W\binom r\ell}. $$
In particular, its sign is exactly the sign of the explicitly computable integer $N(k,p^*)$.
All binomial coefficients involved are at most $2^t$ and thus have $O(t)$ bits. A complete table of binomial coefficients can be computed in polynomial time. Each evaluation of $N(k,p^*)$ uses $O(mt)$ integer operations on numbers whose binary length is polynomial in the input size.
The algorithm is as follows.
To justify step 6, the current conditional expectation is a convex combination of the conditional expectations of its feasible one-coordinate refinements. Therefore, if the current expectation is nonnegative, at least one feasible refinement also has nonnegative expectation.
After all coordinates have been assigned, there is exactly one completion. Thus the final conditional expectation is the actual balance:
$$ B_\mu(p)= \mathbb E[B_\mu(p)\mid p]. $$
The maintained invariant gives $B_\mu(p)\ge0$. Also, $|p|=k^*\ge h$ in the normalized instance, so after undoing the coordinate flips,
$$ d_H(p,q)=t-k^* \le t-\left(\left\lfloor\frac t2\right\rfloor+1\right) = \left\lfloor\frac{t-1}{2}\right\rfloor. $$
There are $O(t)$ initial and refinement expectation computations, each requiring $O(mt)$ polynomial-bit integer operations. Hence the entire algorithm runs in time polynomial in $t$, $m$, and the binary encoding length of the masses.
The sparse rational formulation does not change the sharp computational boundary:
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes both requested claims for the standard domain $t\ge1$:
The arithmetic, averaging identity, conditional-expectation computation, and derandomization are internally consistent. The only issue is that the write-up does not state $t\ge1$. If $t=0$ is permitted literally, the constructive claim is false as stated.
Taking
$$ W=\prod_i b_i,\qquad w_i=a_iW/b_i $$
produces integers satisfying $\sum_iw_i=W$. Although $W$ may be exponentially large numerically, its bit length is at most $\sum_i\log_2 b_i+O(m)$, so the arithmetic has polynomial bit complexity.
The identity
$$ B_\mu(p)=\frac1W\sum_iw_i\operatorname{sgn}(t-2d_H(v_i,p)) $$
is exact under the declared convention $\operatorname{sgn}(0)=0$. This correctly represents strict supporters, strict opponents, and indifferent voters.
A policy has length $t$, which is polynomial in the explicit sparse input. Hamming distances, the majority policy, the agreement count, and the weighted balance numerator are all computable using polynomially many operations on polynomial-bit integers. Membership in NP is established.
The reduction from the supplied finite-profile NP-hardness result is valid:
$$ B_\mu(p)=\frac{\#\text{ supporters}-\#\text{ opponents}}n. $$
Thus non-losing status and the number of agreements with the majority policy are both preserved. The sparse output has at most $n$ types and polynomial encoding length.
Given the finite-profile NP-hardness statement supplied in USER_TASK, this establishes NP-hardness at $k=\lfloor t/2\rfloor+2$. Combined with membership in NP, the claimed NP-completeness follows.
Flipping precisely the coordinates where $q_j=0$ preserves every Hamming distance and converts agreement with $q$ into a one-coordinate:
$$ |\widetilde p|=t-d_H(p,q). $$
After the transformation, each coordinate has mass at least $1/2$ on value $1$. For originally zero-majority coordinates the inequality is strict, since $q_j=0$ means the original mass of ones was strictly below $1/2$.
Thus the normalized majority vector is indeed $1^t$.
The identity
$$ \sum_{x\in H}\beta(x)\operatorname{sgn}(u\cdot x) =C_t\sum_j u_j $$
is proved correctly.
In particular:
No parity or tie case is missing.
Because the normalized coordinate margins satisfy $\delta_j\ge0$, the lemma gives
$$ \mathbb E_{p\in H}[(2|p|-t)B_\mu(p)]\ge0. $$
Partitioning by cardinality is valid. For every $k\ge\lfloor t/2\rfloor+1$, the factors
$$ \Pr(|p|=k)(2k-t) $$
are strictly positive. Therefore at least one conditional mean $\mathbb E[B_\mu(p)\mid |p|=k]$ is nonnegative. This inference is correct.
For a partial policy, the feasible completion count $\binom r\ell$ is correct.
For each ballot type, if $x$ of the selected one-coordinates occur where the ballot has value $1$, then:
$$ \binom{A_v}{x}\binom{Z_v}{\ell-x}. $$
Adding the fixed-coordinate score gives the stated $s_v(x)$. The range of $x$ is exactly the feasible hypergeometric range. Consequently, $N(k,p^*)$ is the exact integer numerator of the conditional expected balance.
The bit-complexity assertion is also sound: all binomial coefficients have $O(t)$ bits, and multiplication and summation with the input weights retain polynomial bit length.
At every partial assignment, the current conditional expectation is a convex combination of the expectations under its feasible zero and one refinements. Therefore a nonnegative current expectation guarantees a feasible refinement with nonnegative expectation.
At the terminal assignment there is one completion, so the conditional expectation equals the actual value $B_\mu(p)$. The invariant therefore proves $B_\mu(p)\ge0$.
Finally,
$$ d_H(p,q)=t-k^* \le t-\left(\left\lfloor\frac t2\right\rfloor+1\right) =\left\lfloor\frac{t-1}{2}\right\rfloor. $$
The equality is correct for both parities of $t$.
There are $O(t)$ cardinality evaluations and $O(t)$ refinement stages, with at most two evaluations per stage. Each evaluation uses polynomially many polynomial-bit integer operations. The algorithm is therefore polynomial in the sparse input length.
The argument silently assumes $t\ge1$. Under the literal possibility $t=0$,
$$ k=\left\lfloor\frac02\right\rfloor+1=1, $$
but the unique zero-coordinate policy has zero agreements, and the claimed distance bound is $\lfloor-1/2\rfloor=-1$. The algorithm also has no cardinality $k\in\{1,\ldots,0\}$ to select. The minimum clarification is to state that the number of issues satisfies $t\ge1$.
⟨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.