d4-conf-wine-2022-0026 (d4-conf-wine-2022-0026)

Given a finite support of complete rankings \(\rho\), with positive binary-rational masses \(\mu_\rho\) summing to \(1\), a target candidate \(a\), and a rational threshold \(q\), let \(p_\rho\) be the position of \(a\) in \(\rho\). For each supported type and each \(d\in\{0,\ldots,p_\rho-1\}\), choose mass \(x_{\rho,d}\) to move to the ranking obtained by moving \(a\) up \(d\) adjacent positions, subject to \(\sum_d x_{\rho,d}=\mu_\rho\), \(x_{\rho,d}\ge 0\), and \(\sum_{\rho,d:\,a\text{ ranks above }b}x_{\rho,d}\ge\tfrac12\) for every \(b\ne a\). Is the minimum per-capita swap cost \(\sum_{\rho,d}d\,x_{\rho,d}\) at most \(q\)? The weak pairwise inequalities give the infimum cost for making \(a\) strictly beat every opponent.

Let \(A\) be a set of \(m\ge3\) candidates. A society is given by its support: a list of \(\tau\) distinct strict complete rankings \(\rho\), each with positive binary-rational mass \(\mu_\rho\), with \(\sum_\rho\mu_\rho=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length.
The input also specifies a target candidate \(a\in A\) and a binary-rational threshold \(q\in\mathbb Q\). Let \(p_\rho\) be the position of \(a\), numbered from \(1\), and let \(\rho^{(d)}\) move \(a\) upward by \(d\in\{0,\ldots,p_\rho-1\}\) adjacent positions, preserving the relative order of all other candidates.
Mass may be divided: choose real \(x_{\rho,d}\ge0\) with \(\sum_d x_{\rho,d}=\mu_\rho\). Require \(\sum_{\rho,d:\,a\succ_{\rho^{(d)}}b}x_{\rho,d}\ge\tfrac12\) for every \(b\in A\setminus\{a\}\).
Define \(C(\mu,a)\) as the minimum of \(\sum_{\rho,d}d\,x_{\rho,d}\) over these choices. Pairwise ties are permitted; this score is the infimum cost of obtaining strict pairwise victories, and the decision concerns \(C(\mu,a)\le q\), including equality.

Is deciding whether \(C(\mu,a)\le q\) solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?

For finite electorates, Dodgson score decision is NP-hard; semi-random score decision has no polynomial-time algorithm unless \(\mathrm{NP}=\mathrm{ZPP}\) under neutral, polynomially samplable models admitting a fixed top-\(K\) ranking with probability at least \(1-1/K\), where \(K=\lceil m^{1/d}\rceil\) for a constant \(d>1\). [Xia–Zheng](https://arxiv.org/pdf/2210.08173v1)
The continuous score is the normalized Dodgson Clone score: fractional vote splitting and weak pairwise victories are already defined, with polynomial-time score computation established for finite profiles. [McCabe-Dansted](https://arxiv.org/pdf/1008.1501)

Conclusion

The decision problem is solvable in deterministic time polynomial in \(m,\tau,L\). The proof uses a rational linear feasibility problem with at most \(m\tau\) variables. In particular, it does not enumerate all possible rankings or expand rational masses into individual voters.

1. A finite minimum exists

Let \(P\) denote the set of arrays \(x=(x_{\rho,d})\) satisfying the mass conservation, nonnegativity, and pairwise constraints in the question.

This set is nonempty: set \(x_{\rho,p_\rho-1}=\mu_\rho\) for every supported ranking and all other variables to zero. This moves \(a\) to the top everywhere, giving it pairwise support \(1\) against every opponent.

Furthermore, mass conservation and nonnegativity imply
\(0\le x_{\rho,d}\le\mu_\rho\).
Thus \(P\) is bounded. It is closed because all its constraints are non-strict linear equalities or inequalities. Consequently, \(P\) is compact, and the continuous linear objective attains its minimum on \(P\). Hence the stated \(C(\mu,a)\) is an attained minimum.

2. Exact reduction to rational linear feasibility

For every supported ranking \(\rho\), allowed displacement \(d\), and opponent \(b\), define the constant
\(E_{\rho,d,b}=1\) if \(a\succ_{\rho^{(d)}}b\), and \(E_{\rho,d,b}=0\) otherwise.

Construct the following system, whose unknowns are real numbers \(x_{\rho,d}\):

\[ \begin{aligned} x_{\rho,d}&\ge0 &&\text{for every }\rho,d,\\ \sum_{d=0}^{p_\rho-1}x_{\rho,d}&=\mu_\rho &&\text{for every }\rho,\\ \sum_\rho\sum_{d=0}^{p_\rho-1}E_{\rho,d,b}x_{\rho,d}&\ge\tfrac12 &&\text{for every }b\ne a,\\ \sum_\rho\sum_{d=0}^{p_\rho-1}d\,x_{\rho,d}&\le q. \end{aligned} \]

The first three groups describe exactly \(P\). Therefore:

• If this system is feasible, its feasible point has cost at most \(q\), so \(C(\mu,a)\le q\).
• If \(C(\mu,a)\le q\), an attained minimizer from Section 1 satisfies the entire system.

Thus feasibility is equivalent to the requested decision, including equality at the threshold.

3. Polynomial encoding size and running time

The number of variables is
\(N=\sum_\rho p_\rho\le m\tau\).
Besides nonnegativity, there are \(\tau\) equalities, \(m-1\) pairwise inequalities, and one cost inequality. Replacing each equality with two inequalities leaves polynomially many constraints.

Every matrix coefficient belongs to
\(\{-1,0,1,\ldots,m-1\}\):
the pairwise coefficients are \(0\) or \(1\), and the cost coefficients are displacements. These coefficients require \(O(\log(m+1))\) bits. The right-hand sides consist of the supplied rational masses, the supplied rational threshold, and the constant \(1/2\); their encoding lengths are bounded by the input length.

The coefficients \(E_{\rho,d,b}\) can be constructed by examining each supported ranking and each allowed displacement, in \(O(m^2\tau)\) elementary operations. Even a dense encoding of the resulting system has size polynomial in \(m,\tau,L\).

We now apply the standard polynomial-time rational linear programming feasibility theorem: a finite system of linear inequalities with explicitly encoded rational coefficients can be tested for feasibility over the reals in deterministic time polynomial in its binary encoding length. Its hypotheses hold here because all coefficients are rational and the entire system is explicitly constructed with polynomial size.

This gives the required algorithm. It uses exact rational feasibility, so no numerical tolerance or assumed separation from \(q\) is needed.

4. Strict victories and the cited hardness results

The weak constraints also justify the stated interpretation as an infimum for strict victories. Let \(x^*\) be a weakly feasible minimizer, and let \(y\) be the all-top assignment from Section 1. For \(0<\varepsilon<1\), the assignment
\(x^\varepsilon=(1-\varepsilon)x^*+\varepsilon y\)
preserves all masses. Against every opponent, its pairwise support is at least
\((1-\varepsilon)/2+\varepsilon=(1+\varepsilon)/2>1/2\).
Its cost tends to \(C(\mu,a)\) as \(\varepsilon\) tends to zero. Conversely, every strictly feasible assignment is weakly feasible, so its cost is at least \(C(\mu,a)\). The two infima therefore agree.

The LP relaxation and polynomial computation of Dodgson Clone scores are described by [McCabe-Dansted, Sections 1 and 3](https://arxiv.org/pdf/1008.1501). The argument above additionally verifies polynomial complexity for the specified rational support representation.

The [Xia–Zheng hardness theorem](https://arxiv.org/pdf/2210.08173v1) concerns finite-electorate Dodgson scores. Indivisible ballots impose integer choices; the present problem explicitly permits fractional splitting. That hardness result consequently does not establish hardness of this continuous decision problem.

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned problem: deciding whether \(C(\mu,a)\le q\) is solvable in deterministic polynomial time in \(m,\tau,L\). The argument is correct and rigorous. No major or minor mathematical issues were found.

• Existence of an attained minimum.

The all-top assignment is valid: for each supported ranking, \(p_\rho-1\) is an allowed displacement, and assigning its entire mass to that displacement places \(a\) above every opponent. Since the masses sum to \(1\), every pairwise constraint is satisfied.

Nonnegativity and mass conservation give \(0\le x_{\rho,d}\le\mu_\rho\) for every coordinate. The feasible set is therefore bounded. All constraints are non-strict linear constraints, so it is also closed. It lies in a finite-dimensional real space and is nonempty, hence compact. The linear objective is continuous and attains its minimum. Every hypothesis of the compactness argument is satisfied.

• Equivalence of feasibility and the requested decision.

The indicators \(E_{\rho,d,b}\) represent exactly the pairwise preferences after each allowed move. Consequently, the first three constraint groups describe precisely the assignments permitted by the task.

Adding the cost inequality gives the correct equivalence in both directions: any feasible assignment has cost at most \(q\), and an attained minimizer satisfies this inequality whenever \(C(\mu,a)\le q\). The attainment argument justifies the reverse direction even when \(C(\mu,a)=q\).

No restriction on the sign of \(q\) is needed. Negative thresholds yield infeasibility because all objective terms are nonnegative.

• Variable count and encoding size.

Each ranking contributes exactly \(p_\rho\) variables, including displacement zero. Thus \(N=\sum_\rho p_\rho\le m\tau\), as claimed.

Converting each mass equality into two inequalities gives \(2\tau+m\) constraints besides nonnegativity, or \(N+2\tau+m\) when nonnegativity is encoded explicitly. Both counts are polynomial.

The stated coefficient range is valid: equality conversion introduces coefficients \(-1\), preference indicators are \(0\) or \(1\), and displacement coefficients range from \(0\) to \(m-1\). Their bit lengths are \(O(\log(m+1))\). Negating a mass when converting an equality changes its encoding length by at most a constant. The supplied rational right-hand sides therefore retain polynomial encoding size.

There are at most \(m\tau(m-1)\) preference indicators. The stated \(O(m^2\tau)\) construction bound is valid, and an explicit dense constraint matrix also has polynomial size. The proof never requires enumerating unsupported rankings or expanding masses into voters.

• Polynomial-time feasibility theorem.

The invoked theorem is stated precisely enough: feasibility over the reals of an explicitly encoded finite rational linear inequality system is decidable deterministically in time polynomial in its binary encoding length.

All its hypotheses are verified. The variables may be real; rational coefficients do not require integral variables or dyadic solutions. Exact feasibility handles infeasibility and threshold equality without numerical tolerances. This establishes the claimed complexity result.

• Strict-victory interpretation.

The convex combination preserves nonnegativity and every mass equality. Each opponent’s support is at least \((1+\varepsilon)/2>1/2\). Linearity makes its cost converge to the weak minimum as \(\varepsilon\) decreases to zero.

Conversely, strict feasibility implies weak feasibility, so every strictly feasible cost is at least \(C(\mu,a)\). Together these statements establish equality of the infima. The prover correctly avoids asserting that the strict infimum is necessarily attained.

• Literature claims and assignment coverage.

McCabe-Dansted explicitly describes polynomial computation of Dodgson Clone scores through rational LP relaxation and discusses weak pairwise victories. The citation is accurate. [McCabe-Dansted](https://arxiv.org/pdf/1008.1501)

Xia–Zheng’s cited hardness result concerns finite ranking profiles and finite-electorate Dodgson score decision. The prover correctly observes that this result does not establish hardness for the fractional problem. Its LP proof independently settles the specified rational support representation. [Xia–Zheng](https://arxiv.org/pdf/2210.08173v1)

No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩