Answer: The implication problem is in \(\mathrm{P}\), and a positive binary-rational violating distribution is computable in polynomial time whenever the implication fails.
Proposition 1 — class: other
Given a finite support \(T\) of complete rankings over options and rational comparative constraints \(V\) on type shares, decide whether every positive distribution \(\mu\) satisfying \(V\) has \(\mu(I)>\mu(J)\), where \(I\) contains types ranking \(a\) above \(b\) and \(J\) contains types ranking \(b\) above \(a\). Return a violating distribution when the implication fails.
Let \(O\) contain \(m\geq 2\) options, let \(a,b\in O\) be distinct, and let \(T\neq\varnothing\) be an explicitly listed set of strict complete rankings of \(O\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau=|T|\) is the support size, not the number of possible rankings; the input specifies \(T\) and constraints on its unknown shares.
For \(E\subseteq T\), write \(\mu(E)=\sum_{t\in E}\mu_t\). A positive distribution satisfies \(\mu_t>0\) for every \(t\in T\) and \(\sum_{t\in T}\mu_t=1\).
The input \(V\) consists of strict comparative constraints \(\mu(E)>\mu(F)\), with explicitly listed disjoint \(E,F\subseteq T\); their coefficients are rational. Promise that some positive distribution satisfies \(V\).
Set \(I=\{t\in T:a\text{ ranks above }b\}\) and \(J=T\setminus I\). Decide whether every positive real distribution satisfying \(V\) has \(\mu(I)>\mu(J)\); if this fails, return a positive binary-rational distribution satisfying \(V\) and \(\mu(I)\leq\mu(J)\).
Is this implication problem in \(\mathrm{P}\), with a violating distribution computable in polynomial time when it fails, or is its decision version \(\mathrm{NP}\)-hard? State running times in \(m,\tau,|V|\), and the total input bit length \(L\).
For finitely many weighted criteria, strict coalition implication under consistent comparative information has a characterization by feasibility of an integer system of nonnegative combination coefficients; this is not a hardness classification ([original result reproduced by an author](https://wassilaouerdane.github.io/HDR_Ouerdane_2022.pdf#page=272)).
No complexity classification for exactly the positive-support distribution problem above was verified.
1. Result
The implication problem is in \(\mathrm{P}\). When the implication fails, a positive rational violating distribution can be computed in polynomial time, with polynomial output bit length. This holds for arbitrary rational coefficients in the listed strict constraints.
The algorithm uses the explicitly listed \(\tau\) rankings; it never enumerates all possible rankings.
2. A linear program that preserves strictness
Enumerate \(T=\{t_1,\ldots,t_\tau\}\), and put \(s=|V|\). Write the constraints in \(V\) as
\[
A_r x>0,\qquad r=1,\ldots,s,
\]
where \(x_i\) denotes the share of \(t_i\). For an unweighted constraint \(\mu(E_r)>\mu(F_r)\), the coefficient \(A_{ri}\) is \(1\) on \(E_r\), \(-1\) on \(F_r\), and \(0\) elsewhere. Rational weighted coefficients are handled identically.
Define \(c_i=1\) when \(t_i\in I\), and \(c_i=-1\) when \(t_i\in J\). Thus
\[
c^\mathsf{T}x=\mu(I)-\mu(J).
\]
Consider the following rational linear program, with variables \(x_1,\ldots,x_\tau,\delta\):
\[ \begin{aligned} \text{maximize}\quad &\delta\\ \text{subject to}\quad &\sum_{i=1}^{\tau}x_i=1,\\ &x_i\geq\delta &&(i=1,\ldots,\tau),\\ &A_r x\geq\delta &&(r=1,\ldots,s),\\ &c^\mathsf{T}x\leq0,\\ &\delta\geq0. \end{aligned} \tag{LP} \]
The target violation remains nonstrict; only positivity and the strict premises receive a common slack.
If feasible, this program has a compact feasible region. Indeed, its constraints imply \(0\leq x_i\leq1\), and summing \(x_i\geq\delta\) gives \(0\leq\delta\leq1/\tau\). The feasible region is closed because all its constraints are nonstrict linear inequalities or equalities. Hence its optimum is attained.
3. Exact correctness proof
Lemma. A positive real distribution satisfying \(V\) and violating the target exists if and only if (LP) is feasible and its optimal value is positive.
Proof. Suppose \(x\) is such a distribution. Every \(x_i\) is positive, and every \(A_r x\) is positive. Because there are finitely many such quantities and \(\tau\geq1\), their minimum
\[
\delta_0=\min\bigl(\{x_i:1\leq i\leq\tau\}
\cup\{A_r x:1\leq r\leq s\}\bigr)
\]
exists and is positive. This definition also covers \(s=0\).
Normalization and the violation give \(\sum_i x_i=1\) and \(c^\mathsf{T}x\leq0\). Therefore \((x,\delta_0)\) is feasible for (LP), so its optimal value is positive.
Conversely, suppose \((x,\delta)\) is feasible with \(\delta>0\). Then \(x_i\geq\delta>0\) for every type, and \(A_r x\geq\delta>0\) for every premise. Normalization makes \(x\) a distribution, and \(c^\mathsf{T}x\leq0\) makes it a violation. This proves both directions. \(\square\)
The algorithm consequently returns:
The promise of consistency is compatible with this argument but is not needed for the reduction. The degenerate cases are also covered: \(I=T\) makes the target automatic, while \(I=\varnothing\) makes every consistent distribution a violation.
4. Exact rational computation and witness size
We use the standard polynomial-time theorem for rational linear programming: in the binary bit model, one can decide feasibility and compute an exact rational optimum and an optimal rational solution whenever a finite optimum exists. Polynomial-time solvability with respect to dimension and binary encoding length is recalled in [Adler and Beling’s paper](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf).
Its hypotheses hold here: every coefficient is rational, the program is explicitly represented, and any feasible region is bounded. Thus the test of whether the optimum is positive is exact.
For completeness, polynomial witness size can also be seen directly. Let \(n=\tau+1\), and let \(B\) be the binary encoding length of (LP). A nonempty optimal face of a bounded polyhedron has a vertex. At that vertex, \(n\) linearly independent active constraints determine the solution.
Clear denominators separately in those constraints. The resulting integer coefficients and right-hand sides have absolute value at most \(H=2^{O(B)}\). By Cramer’s rule, each coordinate is a ratio of integer determinants. The determinant expansion bounds both numerator and denominator in absolute value by \(n!H^n\). Consequently, each coordinate has
\[
O\bigl(n(B+\log n)\bigr)
\]
bits. In particular, a positive optimal slack cannot require a superpolynomial number of bits to distinguish from zero.
When the implication fails, the exact LP solution therefore supplies the requested positive distribution, with numerators and denominators encoded in binary.
5. Running time
Scanning the rankings to determine \(I\) takes \(O(m\tau)\) ranking-entry operations. Constructing the constraint matrix takes \(O(\tau s)\) coefficient positions, besides reading the input.
The program has \(\tau+1\) variables and \(\tau+s+4\) inequalities when normalization is represented by two inequalities. With a dense encoding, its bit length satisfies
\[
B=O\bigl(L+\tau(\tau+s+1)\bigr).
\]
Thus decision and witness computation take
\[
\operatorname{poly}\bigl(m\tau,\ \tau+s,\ L+\tau(\tau+s+1)\bigr)
\]
bit operations. Equivalently, a convenient bound is
\[
\bigl(L+m\tau+\tau(\tau+|V|+1)\bigr)^{O(1)}.
\]
Because rankings and constraints are explicitly listed, all these parameters are polynomially bounded in \(L\). The total running time is therefore polynomial in \(L\), and the witness has polynomial bit length.
6. If “binary-rational” requires dyadic shares
The conclusion also holds under the stronger interpretation that every output share must have denominator a power of two.
Take a rational witness \(x\) with common slack \(\delta>0\), and define
\[
M=\max\bigl(\{1\}\cup\{\|A_r\|_1:1\leq r\leq s\}\bigr),
\qquad
\eta=\frac{\delta}{4M}.
\]
If \(I\) and \(J\) are both nonempty, choose \(i\in I\), \(j\in J\), and transfer mass \(\eta\) from coordinate \(i\) to coordinate \(j\), obtaining \(z\). Every coordinate remains at least \(3\delta/4\). Each premise changes by at most \(M\eta=\delta/4\), so its slack remains at least \(3\delta/4\). Moreover,
\[
c^\mathsf{T}z=c^\mathsf{T}x-2\eta\leq-2\eta.
\]
If \(I=\varnothing\), take \(z=x\); then \(c^\mathsf{T}z=-1\leq-2\eta\). The case \(J=\varnothing\) cannot admit a witness.
Choose a power of two \(N>4M\tau/\eta\). Round the first \(\tau-1\) coordinates of \(z\) downward to multiples of \(1/N\), and set the last coordinate to one minus their sum. Call the result \(y\). Then
\[
\|y-z\|_1<\frac{2\tau}{N}<\frac{\eta}{2M}.
\]
This perturbation preserves positivity, changes each premise by less than \(\eta/2\), and changes the target difference by less than \(\eta/2\). Hence \(y\) is a positive dyadic distribution satisfying every premise and still violating the target strictly. The required \(\log N\), and therefore the construction time and output size, are polynomial in the input length.
7. Relation to the integer characterization
The cited [Proposition 1, reproduced on PDF page 272](https://wassilaouerdane.github.io/HDR_Ouerdane_2022.pdf#page=272), gives an integer-coefficient characterization of coalition implication. Such a characterization does not establish hardness: the explicit positive-support problem here is decided directly by the rational linear program above.
Thus its decision version is in \(\mathrm{P}\); under polynomial-time many-one reductions, it could be \(\mathrm{NP}\)-hard only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the assigned positive-support implication problem. The LP correctly handles strict premises, strictly positive shares, and the nonstrict target violation. Exact rational optimization supplies a polynomial-size witness. The additional dyadic construction is also valid.
No major or minor mathematical issues were found.
The prover uses one variable for each explicitly listed type, so the dimension depends on the support size \(\tau\), not on the number of possible rankings.
For each listed comparative constraint, the corresponding row \(A_r\) correctly expresses the premise as \(A_rx>0\). For the unweighted constraints, disjointness of the coalitions gives precisely the stated coefficients. Explicit rational weighted coefficients remain rational LP data.
Because each ranking is strict and complete, each type belongs to exactly one of \(I\) and \(J\). Consequently, the definition of \(c\) correctly gives \(c^\mathsf{T}x=\mu(I)-\mu(J)\).
Assessment: correct.
The common slack is imposed on exactly the conditions that must be strict: all coordinates and all premises. The target violation correctly remains \(c^\mathsf{T}x\leq0\), including equality.
The compactness argument is valid:
Thus every nonempty feasible region is compact, and the continuous objective attains its maximum.
Assessment: correct; no closure relaxation is incorrectly treated as a strict witness.
Both directions of the lemma are valid.
Starting from a violating positive real distribution, every coordinate and premise value is strictly positive. There are finitely many such values, and the coordinate collection is nonempty because \(\tau\geq1\). Their minimum is therefore positive. Using that minimum as the slack gives a feasible LP point with positive objective.
Conversely, any feasible point with positive slack satisfies every required coordinate positivity condition and every strict premise, while preserving normalization and the target violation.
The empty-premise case is handled correctly: when \(|V|=0\), the minimum is still taken over the nonempty coordinate collection.
Assessment: the equivalence holds over real distributions, as required by the task.
Since the LP imposes \(\delta\geq0\), a feasible instance has a nonnegative optimum. The three relevant outcomes are therefore correctly classified:
The stated extreme cases are also correct. If \(I=T\), every normalized distribution has target difference \(1\). If \(I=\varnothing\), every normalized distribution has target difference \(-1\), and the consistency promise ensures an admissible violation exists.
The consistency promise is unnecessary for the LP equivalence itself; it only excludes vacuous implication caused by inconsistent premises.
Assessment: correct.
The prover explicitly states the needed theorem: rational LP feasibility and exact optimization, including an optimal rational solution when the optimum is finite, are computable in polynomial time in the binary bit model.
All relevant hypotheses are satisfied:
The cited [Adler–Beling paper](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf) recalls polynomial-time solvability of rational LPs in the number of coefficients and total binary encoding length. The theorem invoked is a standard exact rational LP result, and its application here is valid.
Assessment: correct. The sign test is exact, not an unsupported numerical tolerance test.
The determinant argument is valid.
A nonempty optimal face of a bounded polyhedron has a vertex, and such a vertex is also a vertex of the original polyhedron. In ambient dimension \(n=\tau+1\), a vertex is determined by \(n\) linearly independent active constraints, including equality constraints when needed.
Clearing denominators separately in the selected constraints produces integer entries of magnitude at most \(2^{O(B)}\). Cramer’s rule then expresses coordinates as determinant ratios. The bound \(n!H^n\) applies to both numerator and denominator determinants, and the denominator determinant is nonzero by linear independence.
The resulting coordinate bit bound \(O(n(B+\log n))\) is polynomial. The exact polynomial-time LP theorem separately ensures that the solution actually returned has polynomial output length.
Assessment: correct.
The stated preprocessing bounds are appropriate:
The LP has \(\tau+1\) variables. Its inequality count is correctly computed as \(\tau+|V|+4\) when normalization becomes two inequalities.
The dense encoding bound \(B=O(L+\tau(\tau+|V|+1))\) accounts for the original rational data and the added matrix entries. Consequently, the stated bit-operation bound \((L+m\tau+\tau(\tau+|V|+1))^{O(1)}\) is valid.
Explicit listing ensures these parameters are polynomially bounded in \(L\). No strong polynomial-time claim is made or needed.
Assessment: correct; the requested parameter dependence is supplied.
The stronger witness claim also withstands verification.
For the transfer step, \(M\geq1\) gives \(\eta\leq\delta/4\), so removing \(\eta\) from the selected coordinate preserves the asserted coordinate lower bound. Each premise changes by at most \(|A_{rj}-A_{ri}|\eta\leq\|A_r\|_1\eta\leq M\eta\). The target difference decreases by exactly \(2\eta\).
If \(I=\varnothing\), the target difference is \(-1\). Since \(\delta\leq1/\tau\) and \(M\geq1\), the asserted inequality \(-1\leq-2\eta\) is valid.
The rounding construction preserves normalization and produces dyadic shares. Its total perturbation satisfies the stated bound \(\|y-z\|_1<2\tau/N<\eta/(2M)\). These bounds preserve positivity and every strict premise, and leave the target difference strictly negative.
Finally, the rational slack and \(M\) have polynomial encoding length, so a power of two satisfying the threshold can be chosen with polynomially many bits. The construction also covers \(\tau=1\), when there are no coordinates to round downward.
Assessment: correct under both interpretations of “binary-rational.”
The cited [Proposition 1 on PDF page 272](https://wassilaouerdane.github.io/HDR_Ouerdane_2022.pdf#page=272) does give the described integer-coefficient characterization. The prover uses it only for context, not as a premise of the LP proof.
Correctly, an integer feasibility characterization alone does not establish hardness. The final conditional statement about NP-hardness follows from the polynomial-time algorithm under the stated reduction convention.
Required repair or clarification: none.
⟨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.