Answer: \(\mathrm{NP}\)-hard; indeed, the problem is both \(\mathrm{NP}\)-hard and \(\mathrm{coNP}\)-hard and belongs to \(\Sigma_2^p\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDeciding whether an instance I = P admits a Con- dorcet winner is co-NP-hard in the unweighted setting with odd 𝑛.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(t\) and a finite-support rational distribution \(\mu=(\mu_v)_{v\in\{\pm1\}^t}\) with \(\sum_v\mu_v=1\), decide whether there exists \(p\in\{\pm1\}^t\) such that for every \(p'\in\{\pm1\}^t\), \(D_\mu(p,p'):=\sum_v\mu_v\operatorname{sgn}\!\left(\frac{1}{t}\sum_{j=1}^t v_j(p_j-p'_j)\right)\ge0\).
Definitions. The input is \(t\) and a rational distribution \(\mu\), given by its finite support \(\{(v,\mu_v)\}\) with \(v\in\{\pm1\}^t\), \(\mu_v\ge0\), and \(\sum_v\mu_v=1\). Let \(\operatorname{sgn}(x)\in\{-1,0,1\}\) be the sign of \(x\), and define \(\Delta_\mu(p,q)=\sum_v\mu_v\operatorname{sgn}(\langle v,p-q\rangle)\). A proposal \(p\in\{\pm1\}^t\) is a Condorcet winner if \(\Delta_\mu(p,q)\ge0\) for every \(q\in\{\pm1\}^t\).
Target. Is deciding whether such a Condorcet winner exists solvable in polynomial time, or is it NP-hard?
Nearest known results. For finite unweighted profiles with an odd number of voters, deciding whether a Condorcet winner exists is co-NP-hard. Such profiles embed into the distributional formulation through their empirical distributions, so the distributional problem is also co-NP-hard.
The problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. Together with the stated embedding of odd unweighted profiles, it is both \(\mathrm{NP}\)-hard and \(\mathrm{coNP}\)-hard. It also belongs to \(\Sigma_2^p\).
Consequently, a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
Fix \(p\in\{\pm1\}^t\). Every proposal \(q\) is uniquely specified by the set
$$ S=\{i:q_i=-p_i\}. $$
Write this proposal as \(q^S\). Then
$$ \langle v,p-q^S\rangle =2\sum_{i\in S}v_ip_i, $$
and hence
$$ \Delta_\mu(p,q^S) = \mathbb E_{v\sim\mu} \left[ \operatorname{sgn}\left(\sum_{i\in S}v_ip_i\right) \right]. $$
In particular, for \(S=\{i\}\),
$$ \Delta_\mu(p,q^{\{i\}}) =p_i\,\mathbb E_\mu[v_i]. $$
Thus every Condorcet winner satisfies
$$ p_i\mathbb E_\mu[v_i]\ge 0 $$
for every coordinate \(i\). Coordinates with strictly positive expectation are therefore forced to \(+1\), while zero-expectation coordinates can encode Boolean choices.
Consider seven local coordinates
$$ I=\{a_0,a_1,a_2,a_3,x,y,z\}, $$
where the \(a_i\) are anchors and \(x,y,z\) encode the three literals of a clause.
For \(T\subseteq I\), define the character
$$ \chi_T(u)=\prod_{i\in T}u_i. $$
Let
$$ \begin{aligned} h(u)={}&u_{a_0}+15u_{a_1}+u_{a_2}+u_{a_3} +\frac{40}{3}u_{a_0}u_{a_1}u_{a_3}\\ &-8u_{a_0}u_{a_1}u_x -8u_{a_0}u_{a_1}u_y\\ &-\frac{46}{3} u_{a_0}u_{a_1}u_{a_2}u_{a_3}u_xu_yu_z. \end{aligned} $$
Set
$$ \varepsilon=\frac{3}{188}, \qquad \nu(u)=2^{-7}\bigl(1+\varepsilon h(u)\bigr). $$
The sum of the absolute values of the coefficients of \(h\) is
$$ 1+15+1+1+\frac{40}{3}+8+8+\frac{46}{3} =\frac{188}{3}. $$
Therefore \(1+\varepsilon h(u)\ge 0\) for every \(u\). Moreover, every character appearing in \(h\) is nonconstant, so its uniform average is zero. Consequently,
$$ \sum_{u\in\{\pm1\}^7}\nu(u)=1. $$
Thus \(\nu\) is a rational distribution with at most \(128\) support points.
Fourier orthogonality gives
$$ \begin{aligned} \mathbb E_\nu[u_{a_0}]&=\varepsilon,& \mathbb E_\nu[u_{a_1}]&=15\varepsilon,\\ \mathbb E_\nu[u_{a_2}]&=\varepsilon,& \mathbb E_\nu[u_{a_3}]&=\varepsilon, \end{aligned} $$
whereas
$$ \mathbb E_\nu[u_x] = \mathbb E_\nu[u_y] = \mathbb E_\nu[u_z] =0. $$
Also, the complete marginal of \((u_x,u_y,u_z)\) is uniform, because every term of \(h\) contains at least one anchor coordinate.
Let \(\eta\) be an independent uniform element of \(\{\pm1\}\). For a local proposal
$$ r=(1,1,1,1,r_x,r_y,r_z), $$
a set \(L\subseteq I\), and an integer \(D\), define
$$ G_r(L,D)= \mathbb E_{u\sim\nu,\eta} \left[ \operatorname{sgn} \left( \sum_{i\in L}u_ir_i+\eta D \right) \right]. $$
Then:
$$ r^-=(1,1,1,1,-1,-1,-1), $$
one has
$$ G_{r^-}(I,0)=-\varepsilon. $$
Put \(d=|D|\), \(\ell=|L|\), and define
$$ \begin{aligned} \kappa_{\ell,k,d} ={}&2^{-\ell-1} \sum_{\alpha=0}^k \sum_{\beta=0}^{\ell-k} \binom{k}{\alpha} \binom{\ell-k}{\beta} (-1)^\alpha\\ &\quad\cdot \left[ \operatorname{sgn}\bigl(\ell-2(\alpha+\beta)+d\bigr) + \operatorname{sgn}\bigl(\ell-2(\alpha+\beta)-d\bigr) \right]. \end{aligned} $$
This is the Fourier coefficient of the symmetrized threshold function associated with \(L\) and \(d\). Integrating coordinates outside \(L\) gives
$$ \begin{aligned} \varepsilon^{-1}G_r(L,D) ={}&A_L\kappa_{\ell,1,d}\\ &+ \left( \frac{40}{3}\mathbf 1_{\{a_0,a_1,a_3\}\subseteq L} -8r_x\mathbf 1_{\{a_0,a_1,x\}\subseteq L} -8r_y\mathbf 1_{\{a_0,a_1,y\}\subseteq L} \right)\kappa_{\ell,3,d}\\ &-\frac{46}{3} r_xr_yr_z\mathbf 1_{L=I}\kappa_{7,7,d}, \end{aligned} $$
where
$$ A_L= \mathbf 1_{a_0\in L} +15\mathbf 1_{a_1\in L} +\mathbf 1_{a_2\in L} +\mathbf 1_{a_3\in L}. $$
Substitution into this formula gives the following exact minima, taken over all \(L\) of cardinality \(\ell\) and all seven triples \((r_x,r_y,r_z)\ne(-1,-1,-1)\):
| \(\ell\) | \(d=0\) | \(d=1\) | \(d=2\) | \(d=3\) | \(d=4\) | \(d=5\) | \(d=6\) | \(d=7\) |
|---:|---:|---:|---:|---:|---:|---:|---:|---:|
| \(0\) | \(0\) | | | | | | | |
| \(1\) | \(0\) | \(0\) | | | | | | |
| \(2\) | \(0\) | \(0\) | \(0\) | | | | | |
| \(3\) | \(0\) | \(0\) | \(0\) | \(0\) | | | | |
| \(4\) | \(\frac38\) | \(\frac38\) | \(\frac14\) | \(0\) | \(0\) | | | |
| \(5\) | \(\frac34\) | \(\frac58\) | \(\frac12\) | \(\frac5{16}\) | \(0\) | \(0\) | | |
| \(6\) | \(\frac{15}{16}\) | \(\frac{15}{16}\) | \(\frac{45}{64}\) | \(\frac{15}{32}\) | \(\frac9{32}\) | \(\frac1{32}\) | \(\frac1{64}\) | |
| \(7\) | \(0\) | \(\frac{365}{96}\) | \(\frac16\) | \(\frac{89}{48}\) | \(\frac16\) | \(\frac{31}{96}\) | \(0\) | \(0\) |
All entries are nonnegative. If \(d>\ell\), the two signs in the definition cancel, so \(G_r(L,D)=0\). This proves the first assertion.
For the all-false triple, direct evaluation uses
$$ \kappa_{7,1,0}=\frac5{16}, \qquad \kappa_{7,3,0}=-\frac1{16}, \qquad \kappa_{7,7,0}=-\frac5{16}. $$
Consequently,
$$ \begin{aligned} \varepsilon^{-1}G_{r^-}(I,0) &= 18\cdot\frac5{16} + \left(\frac{40}{3}+8+8\right)\left(-\frac1{16}\right) + \frac{46}{3}\left(-\frac5{16}\right)\\ &=-1. \end{aligned} $$
Hence \(G_{r^-}(I,0)=-\varepsilon\), proving the lemma.
We reduce from \(3\)-SAT restricted to clauses containing three distinct variables. This restriction remains \(\mathrm{NP}\)-complete: clauses with fewer than three variables can be padded with fresh variables in the standard satisfiability-preserving way, and tautological clauses can be removed.
Let the formula have variables \(X_1,\ldots,X_n\) and clauses \(C_1,\ldots,C_m\), with \(m\ge1\).
Create:
Thus
$$ t=n+4m. $$
For clause \(C_c\), order its literals as
$$ \ell_{c,1},\ell_{c,2},\ell_{c,3}. $$
Let \(j(c,r)\) be the variable occurring in \(\ell_{c,r}\), and let
$$ s_{c,r}= \begin{cases} +1,&\text{if }\ell_{c,r}=X_{j(c,r)},\\ -1,&\text{if }\ell_{c,r}=\neg X_{j(c,r)}. \end{cases} $$
To sample from the clause distribution \(\mu^c\):
$$ v_{a_{c,k}}=u_{a_k} $$
for the four private anchors.
$$ v_{X_{j(c,1)}}=s_{c,1}u_x,\qquad v_{X_{j(c,2)}}=s_{c,2}u_y,\qquad v_{X_{j(c,3)}}=s_{c,3}u_z. $$
Finally, define
$$ \mu=\frac1m\sum_{c=1}^m\mu^c. $$
Each \(\mu^c\) has at most \(2^8=256\) support points. Therefore \(\mu\) has at most \(256m\) explicitly listed atoms before identical atoms are merged. All probabilities are rational with polynomial encoding length, so the construction is polynomial-time.
For an anchor \(a_{c,k}\), its expectation under its own clause component is respectively
$$ \varepsilon,\quad 15\varepsilon,\quad \varepsilon,\quad \varepsilon. $$
Every other clause component treats this anchor as an outside coordinate \(\eta\), whose expectation is zero. Hence
$$ \mathbb E_\mu[v_{a_{c,k}}]>0. $$
By the singleton-flip inequality, every Condorcet winner must set every anchor to \(+1\).
Every variable coordinate has expectation zero: when it is local to a clause, its \(u_x,u_y,u_z\) marginal is zero, and otherwise it equals the mean-zero variable \(\eta\). Thus the variable coordinates of a possible winner are unrestricted and naturally encode a Boolean assignment.
Let \(\tau\in\{\pm1\}^n\) satisfy the formula. Define \(p\) by
$$ p_{X_j}=\tau_j $$
and set every anchor coordinate to \(+1\).
Consider any flip set \(S\). For clause \(C_c\), the local proposal seen by its gadget is
$$ r_c= \left( 1,1,1,1, s_{c,1}\tau_{j(c,1)}, s_{c,2}\tau_{j(c,2)}, s_{c,3}\tau_{j(c,3)} \right). $$
Because \(C_c\) is satisfied, at least one of the last three entries is \(+1\).
Let \(L_c\) be the intersection of \(S\) with the seven local coordinates of \(C_c\). All selected outside coordinates equal \(\eta\), so their combined contribution has the form \(\eta D_c\) for an integer \(D_c\). Lemma 1 therefore gives
$$ \mathbb E_{\mu^c} \left[ \operatorname{sgn} \left( \sum_{i\in S}v_ip_i \right) \right] \ge0. $$
Averaging this inequality over all clauses yields
$$ \Delta_\mu(p,q^S)\ge0. $$
Since this holds for every \(S\), \(p\) is a Condorcet winner.
Let \(p\) be a Condorcet winner. By Lemma 2, all its anchors equal \(+1\). Interpret its variable coordinates as an assignment \(\tau\).
Suppose that some clause \(C_c\) is false. Then all three corresponding literal signs are \(-1\). Let \(S\) consist of exactly the seven local coordinates of \(C_c\).
Under \(\mu^c\), Lemma 1 gives
$$ \mathbb E_{\mu^c} \left[ \operatorname{sgn} \left( \sum_{i\in S}v_ip_i \right) \right] =-\varepsilon. $$
Now consider a different clause \(C_{c'}\). The set \(S\) contains none of its private anchors, so its selected local coordinates consist only of shared variable coordinates. Their joint marginal is uniform. All selected coordinates outside \(C_{c'}\) equal the independent uniform sign \(\eta\). The simultaneous negation of the selected local variables and \(\eta\) negates the total sum while preserving its distribution. Since \(\operatorname{sgn}\) is odd, the corresponding expected sign is zero.
It follows that
$$ \Delta_\mu(p,q^S) = -\frac{\varepsilon}{m} <0, $$
contradicting that \(p\) is a Condorcet winner. Therefore every clause is satisfied.
Combining Lemmas 3 and 4,
$$ \varphi\text{ is satisfiable} \quad\Longleftrightarrow\quad (\,t,\mu\,)\text{ admits a Condorcet winner}. $$
This proves \(\mathrm{NP}\)-hardness.
The known odd-unweighted result of [Baharav, Constantinescu, and Wattenhofer](https://www.ac.tuwien.ac.at/comsoc2025/comsoc2025-papers/112.pdf) gives \(\mathrm{coNP}\)-hardness. Indeed, an unweighted profile embeds by assigning each voter mass \(1/N\), without changing any pairwise majority inequality.
Finally, the problem lies in \(\Sigma_2^p\). It has the form
$$ \exists p\in\{\pm1\}^t\; \forall q\in\{\pm1\}^t: \Delta_\mu(p,q)\ge0, $$
and the innermost predicate can be evaluated exactly in polynomial time from the explicit rational support.
Thus the established classification is
$$ \text{$\mathrm{NP}$-hard and $\mathrm{coNP}$-hard, and contained in $\Sigma_2^p$.} $$
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes \(\mathrm{NP}\)-hardness by a polynomial-time many-one reduction from restricted \(3\)-SAT. The additional claims of \(\mathrm{coNP}\)-hardness and membership in \(\Sigma_2^p\) are also justified. No substantive gaps were found.
The output fully resolves the requested dichotomy by establishing \(\mathrm{NP}\)-hardness.
⟨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.