Answer: Polynomial-time solvable in \(m,\tau,L,k\), with exact identification of \(+\infty\).
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor plurality and for veto, #POSSIBLE- WINNER is #P-hard even if there is at most one undeter- mined pair of candidates in every partial vote.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a target \(p\), and partial-ballot types \(t\) with rational masses \(\mu_t\), each allowing one or two rankings, independently complete each ballot uniformly among its type's allowed rankings. For \(N\) divisible by the mass denominators, let \(P_N\) be the probability that \(p\) is the unique plurality winner among \(N\mu_t\) ballots of each type. Compute \(I_p(\mu)=\lim_{N\to\infty}-N^{-1}\ln P_N\), taking \(I_p(\mu)=+\infty\) if a unique \(p\)-winning completion is infeasible. When it is feasible, equivalently compute \(\inf_{z\in W_p^+}\sum_t\mu_tD(z_t\Vert u_t)\), where \(z_t\) is a distribution over type \(t\)'s rankings, \(u_t\) is uniform, and \(W_p^+\) imposes strict plurality victory for \(p\).
Let \(C\) be a nonempty set of \(m\) candidates and \(p\in C\). Each ballot type \(t\) is a partial preference order with at most one incomparable pair; its allowed rankings \(A_t\) are all its linear extensions, hence one strict ranking or two differing by an adjacent swap.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total bit length of the society and candidate data.
For each positive integer \(N\) divisible by all mass denominators, independently complete the \(N\mu_t\) ballots of each type uniformly over \(A_t\). Let \(P_N\) be the probability that \(p\) is the unique plurality winner; ties do not count as victories.
Define \(I_p(\mu)=\lim_{N\to\infty}-N^{-1}\ln P_N\), along these admissible integers, with \(-\ln 0=+\infty\).
Equivalently, let \(z_t\) range over distributions on \(A_t\), let \(u_t\) be uniform there, and define \(s_c(z)=\sum_t\mu_t\sum_{r\in A_t:\,c\text{ is first in }r}z_t(r)\) and \(W_p^+=\{z:s_p(z)>s_c(z)\text{ for every }c\ne p\}\).
Then \(I_p(\mu)=\inf_{z\in W_p^+}\sum_t\mu_t D(z_t\Vert u_t)\), where \(D\) is Kullback–Leibler divergence using natural logarithms and the infimum of the empty set is \(+\infty\).
For finite values, computational evaluation means obtaining a rational approximation with additive error at most \(2^{-k}\), for an input positive integer \(k\); infinite values must be identified exactly.
Is evaluation of \(I_p(\mu)\) solvable in time polynomial in \(m,\tau,L,k\), or is it NP-hard?
Counting unique-winning completions in the discrete model is \(\#\mathrm{P}\)-hard even with at most one incomparable pair per ballot ([Bachrach, Betzler, and Faliszewski](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/main-52.pdf)).
No result settling this specific continuous rate-evaluation problem was located in the literature search.
Result. Evaluation of \(I_p(\mu)\), including exact identification of infinite values, is solvable in time polynomial in \(m,\tau,L,k\).
The proof uses the given variational characterization. The essential points are to test strict winning feasibility exactly and to justify polynomial bit complexity despite the entropy function’s unbounded derivatives at the boundary.
1. Reduction to a convex function of at most one variable per supported type
Enumerate the one or two extensions of each supported type. This takes polynomial time because each type has at most one incomparable pair.
If both extensions have the same first candidate, the completion distribution does not affect any plurality score. Its divergence contribution can therefore be minimized independently by choosing the uniform distribution, giving contribution zero. Types with just one extension also contribute zero.
Let \(n\leq\tau\) be the number of remaining types. For type \(j\), write \(w_j>0\) for its mass and \(a_j,b_j\) for the distinct first candidates in its two extensions. Let \(x_j\in[0,1]\) be the probability of choosing the extension headed by \(a_j\).
If \(\beta_c\) denotes the total mass of types whose first candidate is fixed as \(c\), then
\[ s_c(x)=\beta_c+\sum_{j=1}^{n}w_j\bigl(\mathbf 1_{\{a_j=c\}}x_j+\mathbf 1_{\{b_j=c\}}(1-x_j)\bigr). \]
Define \(g_c(x)=s_p(x)-s_c(x)\) for every \(c\neq p\). These are affine functions with rational coefficients.
The objective becomes \(F(x)=\sum_{j=1}^{n}w_j h(x_j)\), where
\[ h(u)=u\ln(2u)+(1-u)\ln(2(1-u)), \]
with the continuous endpoint convention \(0\ln 0=0\). Thus the given characterization says
\[ I_p(\mu)=\inf\{F(x):x\in[0,1]^n,\ g_c(x)>0\text{ for every }c\neq p\}. \]
For \(0<u<1\), differentiation gives \(h'(u)=\ln(u/(1-u))\) and \(h''(u)=1/u+1/(1-u)>0\). Consequently, \(h\) is continuous and convex on \([0,1]\), with minimum zero at \(1/2\) and maximum \(\ln 2\) at the endpoints. Since \(\sum_jw_j\leq1\), we have \(0\leq F(x)\leq\ln 2<1\).
If \(m=1\), return zero. If \(n=0\), all plurality scores are fixed: return zero when \(p\) strictly beats every other candidate, and \(+\infty\) otherwise. Henceforth assume \(m>1\) and \(n>0\).
2. Exact detection of an infinite rate
Consider the rational linear program
\[ \begin{array}{ll} \text{maximize}&\rho\\ \text{subject to}&0\leq\rho\leq1/2,\\ &\rho\leq x_j\leq1-\rho\quad(1\leq j\leq n),\\ &g_c(x)\geq\rho\quad(c\neq p). \end{array} \]
We claim that a strict winning point exists if and only if this program has a positive optimum.
One direction is immediate: a feasible point with \(\rho>0\) satisfies every strict winning inequality.
For the converse, suppose \(x\) is a strict winning point, and put \(\gamma=\min_{c\neq p}g_c(x)>0\). Scores lie in \([0,1]\), so \(\gamma\leq1\). Let \(q=(1/2,\ldots,1/2)\), set \(\lambda=\gamma/4\), and define \(v=(1-\lambda)x+\lambda q\). Every coordinate of \(v\) lies between \(\gamma/8\) and \(1-\gamma/8\). Moreover, \(g_c(q)\geq-1\), and therefore
\[ g_c(v)\geq(1-\lambda)\gamma-\lambda\geq\gamma-2\lambda=\gamma/2. \]
Thus \((v,\gamma/8)\) is feasible for the linear program.
Solve this program using an exact polynomial-time algorithm for rational linear programming. If it is infeasible or its optimum is zero, the strict winning region is empty, and the answer is exactly \(+\infty\).
Otherwise obtain a rational feasible pair \((v,\rho)\) with \(\rho>0\). Its encoding length is polynomial in the input length. In particular, \(\log(1/\rho)\) is polynomially bounded. These are the usual rational linear programming bit bounds: after clearing denominators, a vertex solution has polynomially bounded numerator and denominator lengths by Cramer’s rule and determinant bounds.
3. Replacing strict inequalities after checking feasibility
Suppose the preceding step produced \((v,\rho)\) with \(\rho>0\). Define the compact rational polytope \(K=\{x\in[0,1]^n:g_c(x)\geq0\text{ for every }c\neq p\}\), and let \(V=\min_{x\in K}F(x)\). The minimum exists because \(F\) is continuous.
We claim that \(I_p(\mu)=V\).
Since every strict winning point belongs to \(K\), we have \(V\leq I_p(\mu)\). Conversely, for any \(x\in K\) and any \(0<\alpha<1\), the point \(x_\alpha=(1-\alpha)x+\alpha v\) satisfies
\[ g_c(x_\alpha)\geq\alpha\rho>0. \]
Convexity gives \(F(x_\alpha)\leq(1-\alpha)F(x)+\alpha F(v)\). Letting \(\alpha\) tend to zero yields \(I_p(\mu)\leq F(x)\). Taking \(x\) to be a minimizer proves the claim.
The preceding feasibility test is necessary here. When strict victory is impossible, the weak winning polytope can still contain tied outcomes, whose finite objective values do not represent the rate.
4. Removing the entropy boundary with a controlled error
Let \(\varepsilon=2^{-k}\), \(\delta=\varepsilon/4\), and \(\eta=\delta\rho\). Define
\[ K_\eta=\{x\in K:\eta\leq x_j\leq1-\eta\text{ for every }j\},\qquad V_\eta=\min_{x\in K_\eta}F(x). \]
We have \(V\leq V_\eta\). For the reverse bound, let \(x^\star\) minimize \(F\) over \(K\), and set \(y=(1-\delta)x^\star+\delta v\). Because \(\rho\leq v_j\leq1-\rho\), every coordinate of \(y\) lies in \([\eta,1-\eta]\); its score margins are at least \(\delta\rho\). Hence \(y\in K_\eta\). Convexity and nonnegativity give
\[ V_\eta\leq F(y)\leq(1-\delta)V+\delta F(v)\leq V+\delta\ln2<V+\varepsilon/4. \]
This bound requires no derivative estimate at an endpoint.
The restricted problem has an explicit interior ball. Write \(g_c(x)=d_c+A_cx\). Each coefficient of \(A_c\) has absolute value at most \(2w_j\), so \(\|A_c\|_2\leq\|A_c\|_1\leq2\). Consequently, every point within Euclidean distance \(\rho/4\) of \(v\) has score margins at least \(\rho/2\) and coordinates between \(3\rho/4\) and \(1-3\rho/4\). Since \(\delta\leq1/8\), this ball lies in \(K_\eta\).
Both \(\eta\) and this ball radius have encoding lengths polynomial in \(m,\tau,L,k\).
5. Polynomial-time approximation through weak separation
To make the numerical complexity explicit, use the compact convex epigraph
\[ E=\{(x,t):x\in K_\eta,\ F(x)\leq t\leq2\}. \]
Minimizing the last coordinate over \(E\) gives \(V_\eta\).
We apply the standard weak separation–weak optimization theorem: given an explicitly bounded convex body with a known rational interior ball and a polynomial-time weak separation oracle, a rational linear objective can be optimized to additive accuracy \(\zeta\) in time polynomial in the body’s encoding parameters and \(\log(1/\zeta)\). One output formulation gives a rational point within distance \(\zeta\) of the body whose objective is within \(\zeta\) of optimal. This is the ellipsoid theorem proved by [Grötschel, Lovász, and Schrijver](https://ir.cwi.nl/pub/10046/10046D.pdf), Sections 2–3.
Here are the required hypothesis checks.
First, \(E\) contains the ball of radius \(\rho/4\) centered at \((v,3/2)\). Its \(x\)-coordinates remain in \(K_\eta\), and its last coordinate lies strictly between \(1\) and \(2\), whereas \(F(x)<1\). Also, \(E\) is contained in the ball of radius \(n+2\) with that same center. These bounds have polynomial encoding length.
Second, \(E\) has the following polynomial-time weak separation oracle. Given a rational query \((x,t)\) and tolerance \(0<\xi\leq1\):
For the last case, take any \((x',t')\in E\). Convexity gives
\[ \nabla F(x)\mathbin{\cdot}(x'-x)-(t'-t)\leq t-F(x). \]
The approximation errors and the fact that both \(x,x'\) lie in \([0,1]^n\) imply
\[ a\mathbin{\cdot}\bigl((x',t')-(x,t)\bigr)\leq t-F(x)+\xi/8<-\xi/4. \]
Thus this rational hyperplane strictly separates the query from all of \(E\).
Finally, the required numerical approximations are computable in polynomial time. On the restricted box, \(\partial_jF(x)=w_j(\ln x_j-\ln(1-x_j))\), and all logarithm arguments are positive rationals.
For completeness, logarithms of positive rationals admit polynomial-time absolute approximation. Write a positive rational as \(2^e u\) with \(1\leq u<2\), and use
\[ \ln u=2\sum_{\ell=0}^{\infty}\frac{z^{2\ell+1}}{2\ell+1},\qquad z=\frac{u-1}{u+1}. \]
Here \(0\leq z<1/3\), so the tail decays geometrically. The same series with \(z=1/3\) computes \(\ln2\). To obtain error \(2^{-h}\), polynomially many terms and polynomial-length rational arithmetic suffice, including the additional precision needed for the factor \(e\). Hence the oracle runs in time polynomial in the query length, \(m,\tau,L,k\), and \(\log(1/\xi)\).
All hypotheses of weak optimization are therefore satisfied in the binary computational model.
6. Final error and complexity
Apply weak optimization to minimize the last coordinate over \(E\), with tolerance \(\zeta=\varepsilon/4\). Let its rational output be \((\widehat x,\widehat t)\). The objective guarantee gives \(\widehat t\leq V_\eta+\zeta\). Since this output is within distance \(\zeta\) of \(E\), its last coordinate also satisfies \(\widehat t\geq V_\eta-\zeta\). Therefore \(|\widehat t-V_\eta|\leq\varepsilon/4\).
Combining this with the restriction bound and \(I_p(\mu)=V\) gives
\[ |\widehat t-I_p(\mu)|\leq|\widehat t-V_\eta|+(V_\eta-V)<\varepsilon/2\leq2^{-k}. \]
The algorithm uses only the supported types and rational masses; it never expands a society into individual ballots. Its running time is polynomial in \(m,\tau,L,k\).
The discrete counting hardness stated in the question is compatible with this conclusion: the continuous rate is a convex optimum that can be approximated without counting winning completions.
⟨structured verdict parsed — rendered above⟩
The claimed polynomial-time result is sound in substance. All substantive reductions, feasibility arguments, numerical bounds, and approximation guarantees check out. There is one minor omission in specifying the separation-oracle interface.
The reduction correctly preserves both plurality scores and the minimum divergence.
A type whose extensions have the same first candidate contributes a fixed score, regardless of its completion distribution. Choosing its uniform distribution minimizes its divergence to zero independently of all winning constraints. A singleton type also contributes zero.
For each remaining type, the binary distribution is parametrized by \(x_j\in[0,1]\), and its divergence from the uniform distribution is exactly \(h(x_j)\). The displayed score formula correctly assigns masses \(w_jx_j\) and \(w_j(1-x_j)\) to the two possible first candidates.
The derivatives are correct:
\(h'(u)=\ln(u/(1-u))\) and \(h''(u)=1/u+1/(1-u)>0\).
Continuity at the endpoints follows from the stated convention. Consequently, the bounds \(0\leq h(u)\leq\ln2\) and \(0\leq F(x)\leq\ln2<1\) are correct.
The cases \(m=1\) and \(n=0\) are handled correctly, including fixed ties.
The linear program correctly distinguishes an empty strict-winning region from a nonempty one.
A feasible positive \(\rho\) immediately gives strict victory. Conversely, the proposed perturbation of a strict-winning point moves every coordinate into the interior while preserving positive winning margins.
The constants check out. With \(\lambda=\gamma/4\), each coordinate has distance at least \(\gamma/8\) from either endpoint. Moreover,
\((1-\lambda)\gamma-\lambda\geq\gamma-2\lambda=\gamma/2\),
because \(0<\gamma\leq1\). Thus the proposed pair is feasible.
The rational LP has polynomially many variables and constraints and coefficients of polynomial encoding length. Its feasible region is bounded. The stated rational vertex bounds justify a positive rational witness with polynomial encoding length whenever the optimum is positive. Exact comparison with zero is therefore justified.
This step is valid only after positive strict feasibility has been established, and the proof explicitly respects that condition.
For every \(x\in K\), mixing with the witness \(v\) gives margins at least \(\alpha\rho>0\). Convexity and the finite bound on \(F(v)\) then imply that strict-winning objective values approach \(F(x)\).
Together with the inclusion of the strict-winning region in \(K\), this proves \(I_p(\mu)=V\). Compactness and continuity justify the existence of the minimizer used here.
The restriction error is correct. The point \(y=(1-\delta)x^\star+\delta v\) belongs to \(K_\eta\), and
\(0\leq V_\eta-V\leq\delta\ln2<\varepsilon/4\).
The gradient coefficients of each score margin have absolute values at most \(2w_j\). Hence the asserted bound \(\|A_c\|_2\leq2\) is valid.
The ball of radius \(\rho/4\) around \(v\) preserves margins of at least \(\rho/2\) and coordinate distances of at least \(3\rho/4\) from the endpoints. Since \(k\) is positive, \(\delta\leq1/8\), so this ball lies in \(K_\eta\).
The encoding-length assertions for \(\eta\) and the ball radius follow from the rational witness bounds.
The epigraph \(E\) is compact, convex, and full-dimensional. Its proposed interior ball is valid: throughout that ball, the last coordinate exceeds \(1\), while \(F(x)<1\), and the last coordinate remains below \(2\). The outer radius \(n+2\) is also sufficient.
The approximate-membership branch is correct, including the upper constraint \(t\leq2\): raising \(t\) to \(\max\{t,F(x)\}\) preserves that constraint.
The separating branch also checks out. Gradient approximation contributes at most \(\xi/8\) to the scalar-product error. When that branch is selected, \(t-F(x)<-3\xi/8\), giving the claimed strict separation bound.
The logarithm series is correct. Range reduction gives \(0\leq z<1/3\), and the geometric tail permits polynomial-time absolute approximation. Rational arithmetic and the extra precision for multiplication by \(e\) require only polynomial bit complexity.
The cited theorem supplies the stated weak optimization guarantee for explicitly bounded convex bodies with an interior ball and a suitable weak separation oracle. [Grötschel, Lovász, and Schrijver, Sections 1–3](https://ir.cwi.nl/pub/10046/10046D.pdf).
Minor issue — oracle normalization. The branches returning violated rational linear inequalities do not explicitly specify how their normals satisfy the cited theorem’s normalization convention. This is a routine interface omission; it does not undermine the separation argument or require new mathematics.
Minimum clarification: State the oracle’s normal-vector convention and explicitly require the returned linear-constraint normals to satisfy it while retaining polynomial encoding length.
The weak optimization guarantee gives the stated upper bound on \(\widehat t\). Distance at most \(\zeta\) from \(E\) gives the lower bound \(\widehat t\geq V_\eta-\zeta\). Thus the final additive-error calculation is correct.
The algorithm operates on supported types without expanding the society into individual ballots. Its complexity is polynomial in \(m,\tau,L,k\), and infinite values are identified exactly. The discrete counting hardness does not contradict this conclusion.
⟨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.