Answer: polynomial-time solvable
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a set D of votes, listed explicitly, a po- sition matrix X (which can be realized by an election con- taining only votes from D)7, and a candidate c, it is NP-hard to decide if there is an election realizing X, in which c is a Condorcet winner and all votes come from D. Making partial progress on the general problem, we pro- vide a necessary condition for the existence of an election realizing a given position matrix in which a given candi- date c is a Condorcet winner.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), an explicitly listed set \(D\) of ranking types, a rational bistochastic frequency matrix \(Y\), and candidate \(c\), decide whether there exists a probability distribution \(\mu\) over \(D\) such that \(\mu\) realizes \(Y\) and \(c\) is preferred to every other candidate by mass greater than one half; equivalently, maximize \(\delta\) subject to the realization constraints and all Condorcet margins being at least \(\frac{1}{2}+\delta\), and test whether \(\delta > 0\).
Definitions. Let \(C=\{c_1,\ldots,c_m\}\), let \(D\) be an explicitly listed finite set of complete rankings of \(C\), and let \(Y\in\mathbb{Q}_{\ge 0}^{m\times m}\) be bistochastic. A distribution \(\mu\in\mathbb{R}_{\ge0}^{D}\) realizes \(Y\) if \(\sum_{v\in D}\mu_v=1\) and \(\sum_{v:\,c_j\text{ is in position }i\text{ in }v}\mu_v=Y_{i,j}\) for all \(i,j\). Candidate \(c\in C\) is a Condorcet winner under \(\mu\) if \(\sum_{v:\,c\succ_v d}\mu_v>\tfrac12\) for every \(d\ne c\). Equivalently, define \(\delta=\max_{\mu\text{ realizing }Y}\min_{d\ne c}\bigl(\sum_{v:\,c\succ_v d}\mu_v-\tfrac12\bigr)\).
Target. Given \(C,D,Y,c\), is deciding whether \(\delta>0\) polynomial-time solvable, or NP-hard?
Nearest known results. The discrete counterpart is NP-hard: given an explicitly listed \(D\), a position matrix \(X\) promised realizable using votes from \(D\), and \(c\), deciding whether some finite election realizing \(X\), using only votes from \(D\), makes \(c\) a Condorcet winner is NP-hard.
For explicitly listed \(D\), deciding whether \(\delta>0\) is polynomial-time solvable.
This remains true without a promise that \(Y\) is realizable: unrealizable instances can be rejected by the same linear program.
For every ranking \(v\in D\), position \(i\), and candidate \(c_j\), define
\(A_{i,j,v}=1\) if \(c_j\) occupies position \(i\) in \(v\), and \(A_{i,j,v}=0\) otherwise.
For every opponent \(d\neq c\), define
\(B_{d,v}=1\) if \(c\succ_v d\), and \(B_{d,v}=0\) otherwise.
Introduce one variable \(\mu_v\) for every \(v\in D\), together with a common-margin variable \(t\). Consider the rational linear program
\(\max t\),
subject to
\(\sum_{v\in D}\mu_v=1\),
\(\sum_{v\in D}A_{i,j,v}\mu_v=Y_{i,j}\) for all \(i,j\),
\(\sum_{v\in D}B_{d,v}\mu_v-\frac12\ge t\) for every \(d\neq c\),
\(\mu_v\ge0\) for every \(v\in D\),
and
\(-\frac12\le t\le\frac12\).
The bounds on \(t\) do not change the optimum whenever \(Y\) is realizable, because every pairwise probability lies in \([0,1]\).
Let \(P(Y)\) denote the set of distributions on \(D\) realizing \(Y\). It is the intersection of the probability simplex with finitely many affine subspaces. Consequently, \(P(Y)\) is compact whenever it is nonempty.
Fix any \(\mu\in P(Y)\). For this fixed \(\mu\), the largest feasible value of \(t\) is
\(\min_{d\neq c}\left(\sum_{v:\,c\succ_v d}\mu_v-\frac12\right)\).
Therefore, maximizing jointly over \(\mu\) and \(t\) gives exactly
\(t^\star=\max_{\mu\in P(Y)}\min_{d\neq c}\left(\sum_{v:\,c\succ_v d}\mu_v-\frac12\right)=\delta\).
The maximum is attained because the objective is continuous and \(P(Y)\) is compact.
We now verify the strict winner condition.
\(\gamma_d=\sum_{v:\,c\succ_v d}\mu_v-\frac12>0\).
There are only finitely many opponents, so \(\gamma=\min_{d\neq c}\gamma_d>0\). The pair \((\mu,\gamma)\) is feasible for the linear program. Hence \(t^\star\ge\gamma>0\).
\(\sum_{v:\,c\succ_v d}\mu^\star_v-\frac12\ge t^\star>0\).
Thus \(\mu^\star\) realizes \(Y\) and makes \(c\) a Condorcet winner.
Hence the answer is yes exactly when the optimum of this rational linear program is strictly positive.
If \(P(Y)=\varnothing\), the linear program is infeasible, so the instance is rejected. If \(m=1\), the Condorcet condition is vacuous and the answer is yes exactly when \(Y\) is realizable; this is again linear-program feasibility.
Let \(q=|D|\). The linear program has \(q+1\) variables, \(m^2+1\) equality constraints, \(m-1\) pairwise-margin constraints, \(q\) nonnegativity constraints, and two bounds on \(t\).
All coefficients are among \(0\), \(1\), \(\frac12\), and the rational entries of \(Y\). Because every ranking in \(D\) is explicitly listed, all coefficients \(A_{i,j,v}\) and \(B_{d,v}\) can be constructed in time polynomial in the input length. The resulting LP has polynomial encoding length.
The standard bit-complexity theorem for rational linear programming therefore computes its optimum and compares it with \(0\) in polynomial time. In particular, strictness causes no numerical ambiguity: a finite rational LP optimum is attained at a rational basic feasible solution whose numerator and denominator have polynomially bounded bit length. Consequently, if \(t^\star\neq0\), then \(|t^\star|\ge2^{-p(L)}\) for some polynomial \(p\), where \(L\) is the input length. Thus \(t^\star>0\) can be distinguished exactly from \(t^\star=0\) in polynomial time.
There is no contradiction with hardness for an exact integral position matrix.
Suppose the discrete matrix \(X\) records position counts for exactly \(n\) voters, and let \(Y=X/n\). The discrete formulation requires integer variables \(x_v\ge0\) satisfying
\(\sum_v x_v=n\)
and
\(\sum_v A_{i,j,v}x_v=X_{i,j}\).
The continuous formulation replaces these by unrestricted rational masses \(\mu_v\). If a rational continuous solution exists, clearing denominators produces a finite election with some electorate size \(N\), but its count matrix is
\(NY=\frac{N}{n}X\),
which need not equal the originally prescribed count matrix \(X\). Thus fractional feasibility allows the electorate size—and hence a common scaling of all position counts—to change. The discrete hardness can reside precisely in requiring an integral decomposition at the fixed scale \(n\).
Indeed, because the LP is rational, every positive continuous solution can be scaled to a finite election whose normalized position matrix is \(Y\). Therefore, if the quoted discrete problem instead allowed an arbitrary electorate size and prescribed only normalized position frequencies, it would be equivalent to the polynomial-time LP above; the claimed NP-hardness would then require a different interpretation.
The target problem belongs to \(\mathrm{P}\). The explicit listing of \(D\) is decisive: it gives one LP variable per permitted ranking and makes every positional and pairwise-majority condition an explicitly available linear constraint.
⟨structured verdict parsed — rendered above⟩
The prover correctly reduces the continuous problem to a rational linear program of polynomial encoding length. For \(m\ge 2\) and realizable \(Y\), the LP optimum is exactly \(\delta\), and strict positivity can be decided in polynomial time. The central complexity classification is correct.
Two edge-case conventions are not supplied by the problem statement: \(\delta\) is undefined when \(Y\) is unrealizable, and the minimum over opponents is empty when \(m=1\). The prover chooses natural decision conventions for both, but these choices require explicit clarification.
The variables \(\mu_v\), together with
\[ \sum_{v\in D}\mu_v=1,\qquad \sum_{v\in D}A_{i,j,v}\mu_v=Y_{i,j},\qquad \mu_v\ge 0, \]
describe exactly the distributions on \(D\) realizing \(Y\). This part is correct.
The normalization constraint may be redundant when \(Y\) is bistochastic and the positional equations are imposed, but including it is harmless.
For each opponent \(d\ne c\), the constraint
\[ \sum_{v\in D}B_{d,v}\mu_v-\frac12\ge t \]
is equivalent to requiring that \(t\) be at most the pairwise margin against \(d\). Thus, for fixed \(\mu\), maximizing \(t\) gives the minimum of the finitely many pairwise margins. This is correct when \(m\ge2\).
The bounds \(-\frac12\le t\le\frac12\) do not alter the optimum: every pairwise probability lies in \([0,1]\), so every margin lies in \([-\frac12,\frac12]\). This argument is correct.
For nonempty \(P(Y)\) and \(m\ge2\), the equality
\[ t^\star = \max_{\mu\in P(Y)} \min_{d\ne c} \left( \sum_{v:c\succ_v d}\mu_v-\frac12 \right) = \delta \]
follows directly from the LP constraints. The feasible set is a closed subset of a finite-dimensional simplex and is therefore compact. The minimum of finitely many linear functions is continuous, so the maximum is attained. The prover does not explicitly state the latter continuity fact, but it is routine and does not create a substantive gap.
Both directions are correct:
Consequently, for \(m\ge2\) and realizable \(Y\), the answer is yes exactly when \(t^\star>0\).
If \(Y\) is not realizable from \(D\), the LP is infeasible. However, as the task defines it, \(\delta\) is then a maximum over the empty set and has no stated value. The prover declares such instances rejected without specifying a convention such as \(\max\varnothing=-\infty\), or reformulating the decision question as the existence of a realizing distribution making \(c\) a Condorcet winner.
This does not affect the polynomial-time classification, but it is a genuine definitional omission.
The Condorcet-winner condition is indeed vacuous when there are no opponents. Nevertheless, the displayed definition of \(\delta\) contains \(\min_{d\ne c}\) over an empty set. No convention for this minimum is given. Therefore, the statement that “the answer is yes exactly when \(Y\) is realizable” is correct for the existential Condorcet-winner formulation, but it does not literally resolve whether the undefined quantity \(\delta\) is positive.
The minimum clarification needed is either to assume \(m\ge2\), define \(\min\varnothing=+\infty\), or state that the decision problem is the existential formulation rather than literal comparison with \(\delta\) in this edge case.
The size count is correct up to harmless redundancy:
Because every ranking is explicitly listed, constructing all \(A_{i,j,v}\) and \(B_{d,v}\) is polynomial in the input length.
The invocation of polynomial-time rational LP optimization is mathematically appropriate. The bounded feasible region ensures a finite attained optimum whenever the LP is feasible. The basic-feasible-solution bit-length argument supports exact comparison with zero. The prover could state the LP bit-complexity theorem more formally, but its necessary hypotheses and relevant consequence are identified.
The explanation is correct under the prover’s stated interpretation that the discrete matrix \(X\) consists of integral counts for a fixed electorate size \(n\). Clearing denominators can change the electorate size and therefore scales \(X\), so it need not produce a decomposition at the original scale.
The user’s description does not explicitly specify whether \(X\) is a count matrix or a normalized frequency matrix. Thus this reconciliation is conditional on an interpretation, but it is ancillary to the continuous LP argument.
The proof needs only the following clarifications:
⟨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.