Answer: Polynomial-time solvable in \(m,\tau,L\), including the exact optimum and an optimal rational vector.
Theorem 10 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe optimal solution value for Linear Pro- grams 2 and 3 is always identical.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate set \(C\) and a finite support \(T\) of complete rankings with binary-rational masses \(\mu_t\ge 0\) summing to \(1\), define \(w_\mu(a,b)=\sum_{t:a\succ_t b}\mu_t-\sum_{t:b\succ_t a}\mu_t\) and \(E_\mu=\{(a,b):w_\mu(a,b)>0\}\). Compute the optimum and an optimal vector \(x\) of \(\min\sum_{(a,b)\in E_\mu}w_\mu(a,b)x_{ab}\), subject to \(x_{ab}+x_{ba}=1\) for each distinct pair and \(x_{ab}+x_{bc}+x_{ca}\ge 1\) for each distinct triple.
Let \(C\) be a candidate set with \(m=|C|\ge 1\). A society is given by its support: a list \(T\) of \(\tau\) distinct strict complete rankings of \(C\), each with positive binary-rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length. State running times in \(m,\tau,L\).
Define \(w_\mu(a,b)=\sum_{t:a\succ_t b}\mu_t-\sum_{t:b\succ_t a}\mu_t\) and \(E_\mu=\{(a,b):w_\mu(a,b)>0\}\); majority ties contribute no edge.
For every ordered pair of distinct candidates, let \(x_{ab}\in[0,1]\) be a real variable. Compute the exact optimum and any optimal rational vector of \(\min\sum_{(a,b)\in E_\mu}w_\mu(a,b)x_{ab}\), subject to \(x_{ab}+x_{ba}=1\) for all distinct pairs and \(x_{ab}+x_{bc}+x_{ca}\ge 1\) for all ordered triples of distinct candidates.
Is this exact optimization problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite electorates, the pair-and-triangle relaxation has the same optimum as the nonnegative edge-variable relaxation requiring the sum on every directed majority cycle to be at least one. [Conitzer, Davenport, and Kalagnanam](https://www.cs.cmu.edu/~conitzer/kemenyAAAI06.pdf).
No separate complexity result specifically stated for the support-encoded mass formulation was verified.
The exact optimization problem is solvable in time polynomial in \(m,\tau,L\). This includes computing the exact optimum and an optimal rational vector.
The proof uses the explicitly given linear program and polynomial-time exact rational linear programming. It does not require expanding the support into individual voters.
Write each input mass as \(\mu_t=p_t/q_t\), where \(p_t,q_t\) are positive integers encoded in binary. Define
\(Q=\prod_{t\in T}q_t,\qquad h_t=p_t(Q/q_t).\)
Then \(\mu_t=h_t/Q\). Since the masses sum to one,
\(\sum_{t\in T}h_t=Q.\)
The binary length of \(Q\) is \(O(L)\): indeed, \(\log_2 Q=\sum_t\log_2q_t\), and the denominator encodings are part of the input. Consequently, every \(h_t\) also has \(O(L)\) bits.
For distinct candidates \(a,b\), define the integer
\(W_{ab}=\sum_{t:a\succ_t b}h_t-\sum_{t:b\succ_t a}h_t.\)
Thus \(w_\mu(a,b)=W_{ab}/Q\), and \(|W_{ab}|\le Q\). In particular, every majority weight has \(O(L)\) bits, and its sign can be determined exactly.
Constructing position arrays for the rankings permits each comparison \(a\succ_t b\) to be answered directly. Computing all margins then requires \(O(\tau m^2)\) additions or subtractions of integers with \(O(L)\) bits. Including the common-denominator computations, a conservative bound using elementary integer arithmetic is
\(O\bigl((\tau m^2+\tau)L^2\bigr)\)
bit operations.
Set \(c_{ab}=W_{ab}\) when \(W_{ab}>0\), and \(c_{ab}=0\) otherwise. The required objective is exactly
\(\displaystyle \frac1Q\sum_{a\ne b}c_{ab}x_{ab}.\)
Because \(Q>0\), minimizing the integer-coefficient objective \(\sum_{a\ne b}c_{ab}x_{ab}\) gives precisely the same optimal vectors.
If \(m=1\), the optimum is \(0\), and the empty vector is optimal. Hence assume \(m\ge2\).
There are \(n=m(m-1)\) variables. An explicit constraint list consists of:
Thus there are \(O(m^3)\) inequalities. Every constraint coefficient and right-hand side belongs to \(\{-1,0,1\}\). The objective coefficients have \(O(L)\) bits by Section 1.
Even using a dense matrix representation, the total linear-program encoding length \(B\) therefore satisfies
\(B=O(m^5+m^2L).\)
The feasible set is nonempty: assigning \(x_{ab}=1/2\) for every ordered pair satisfies every pair equality, and each triangle sum equals \(3/2\). It is closed and contained in \([0,1]^n\), hence compact. The linear objective therefore attains a finite minimum.
We apply the standard exact rational linear-programming theorem:
A linear program with binary-encoded rational data can be solved in time polynomial in its encoding length. If its feasible set is nonempty and its minimum is finite, an optimal rational solution can be computed.
This is the bit-complexity theorem for linear programming, rather than merely an approximation guarantee. Integer-data feasibility and its reduction to exact optimization through primal-dual feasibility are described in [MIT’s lecture on the ellipsoid method](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
All hypotheses have been checked: our coefficients are integers of polynomial encoding length, the feasible set is nonempty, and the objective attains a finite minimum.
Apply this theorem to the objective \(\sum_{a\ne b}c_{ab}x_{ab}\), obtaining an optimal rational vector \(x^*\). Return \(x^*\) and the exact rational number
\(\displaystyle v^*=\frac1Q\sum_{a\ne b}c_{ab}x^*_{ab}.\)
For some fixed polynomial \(P\), the total running time is bounded by
\(O\bigl((\tau m^2+\tau)L^2\bigr)+P(m^5+m^2L),\)
including polynomial-time exact evaluation of the returned objective. This is polynomial in \(m,\tau,L\).
There is also a particularly simple bound showing that an exact optimal vector need not have a large representation.
A linear objective on a nonempty compact polytope has an optimal vertex. At such a vertex, choose \(n\) linearly independent tight constraint rows, obtaining \(Ax=b\). Here \(A\) is an invertible integer matrix, and each row has at most three nonzero entries, all equal to \(1\) or \(-1\). Hadamard’s determinant inequality gives
\(1\le|\det A|\le3^{n/2}.\)
By Cramer’s rule, all coordinates have a common denominator \(D=|\det A|\). Since each coordinate lies in \([0,1]\), they can be written as \(x_{ab}=k_{ab}/D\), with integers \(0\le k_{ab}\le D\). Each coordinate consequently needs only \(O(n)\) bits, so the whole vector needs \(O(n^2)=O(m^4)\) bits.
Its objective value has the representation
\(\displaystyle \frac{\sum_{a\ne b}c_{ab}k_{ab}}{QD}.\)
The numerator is at most \(nQD\). Hence the exact value needs \(O(L+m^2)\) bits. Exact output therefore presents no exponential-size obstruction.
The pair-and-triangle formulation appears as Linear Program 3 in [Conitzer, Davenport, and Kalagnanam](https://www.cs.cmu.edu/~conitzer/kemenyAAAI06.pdf), where its polynomial size and equality of optimum with the cycle relaxation are established.
For the present complexity question, that equality is unnecessary: the given formulation itself already provides the polynomial-size rational linear program. The support encoding is handled directly by the majority-weight calculation above.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The output establishes a polynomial-time algorithm for the exact optimum and an optimal rational vector in the support-encoded formulation. No major or minor mathematical issues were found.
The common denominator \(Q=\prod_{t\in T}q_t\) is a positive integer, and every \(h_t=p_t(Q/q_t)\) is an integer satisfying \(\mu_t=h_t/Q\). The normalization of the input masses gives \(\sum_t h_t=Q\).
The denominator encodings imply that \(Q\) has \(O(L)\) bits. Positivity and normalization imply \(0<h_t\le Q\), so each \(h_t\) also has \(O(L)\) bits. Consequently, the signed sums \(W_{ab}\) satisfy \(|W_{ab}|\le Q\) and represent the majority weights exactly.
The claimed \(O(\tau m^2)\) integer additions or subtractions correctly accounts for comparing every candidate pair in every support ranking. The stated bit-operation bound \(O((\tau m^2+\tau)L^2)\) conservatively covers these operations and the common-denominator arithmetic. It does not require enumerating individual voters.
Defining \(c_{ab}=W_{ab}\) for positive margins and \(c_{ab}=0\) otherwise includes precisely the directed majority edges. Zero margins contribute nothing, as required.
The original objective equals \(Q^{-1}\sum_{a\ne b}c_{ab}x_{ab}\). Since \(Q>0\), scaling preserves every optimal vector, and dividing the returned objective by \(Q\) recovers the exact requested value.
The variable count \(n=m(m-1)\), bound-inequality count \(2n\), pair-equality count \(\binom m2\), and ordered-triple count \(m(m-1)(m-2)\) are correct. Replacing each pair equality by two inequalities gives an equivalent system. All constraint coefficients and right-hand sides belong to \(\{-1,0,1\}\).
With \(O(m^3)\) rows and \(O(m^2)\) columns, the dense constraint encoding uses \(O(m^5)\) bits. The objective adds \(O(m^2L)\) bits. Thus the stated bound \(B=O(m^5+m^2L)\) is valid.
The assignment \(x_{ab}=1/2\) satisfies the bounds, pair equations, and every applicable triangle inequality. Closedness and boundedness establish compactness and attainment of the minimum.
The case \(m=1\) is explicitly handled correctly. For \(m=2\), the triangle constraints are absent, and the same feasibility and compactness reasoning remains valid. An empty majority-edge set also causes no problem: the objective is identically zero.
The theorem invoked concerns polynomial-time computation with binary-encoded rational data and produces an exact optimal rational solution when the feasible set is nonempty and the minimum is finite. It does not require integrality or full dimensionality of the feasible set.
Every relevant hypothesis is verified in the output: the data are integers of polynomial encoding length, feasibility is established, and the bounded feasible region ensures a finite attained optimum.
The cited [MIT lecture](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf) supports the invocation: slides 28–29 state polynomial-time integer-data feasibility and its reduction to optimization through primal-dual feasibility.
Exact evaluation of \(Q^{-1}\sum_{a\ne b}c_{ab}x^*_{ab}\) is polynomial-time because the returned rational vector has polynomial encoding length. Absorbing this computation into a fixed polynomial \(P\) is legitimate. The displayed total running time is polynomial in \(m,\tau,L\).
A linear objective on a nonempty compact polytope has an optimal vertex. At a vertex, the tight constraint rows contain \(n\) linearly independent rows, including when the polytope lies in a proper affine subspace.
Each selected row has at most three nonzero entries of magnitude one. Hadamard’s inequality therefore gives \(|\det A|\le 3^{n/2}\); integer nonsingularity gives \(|\det A|\ge1\).
Cramer’s rule supplies the common denominator \(D=|\det A|\). The coordinate bounds imply integer numerators \(0\le k_{ab}\le D\). Hence each coordinate uses \(O(n)\) bits, and the full vector uses \(O(n^2)=O(m^4)\) bits.
Since \(c_{ab}\le Q\), the objective numerator is at most \(nQD\). Both numerator and denominator therefore have \(O(L+n+\log n)=O(L+m^2)\) bits. These estimates are valid.
This section establishes the existence of a compactly represented optimal vertex; it does not incorrectly claim that the unspecified LP algorithm necessarily returns a vertex.
The [Conitzer–Davenport–Kalagnanam paper](https://www.cs.cmu.edu/~conitzer/kemenyAAAI06.pdf) presents the pair-and-triangle formulation as Linear Program 3, explicitly describes its polynomial size, and states equality of its optimum with Linear Program 2 in Theorem 10.
The prover does not use that equivalence to establish complexity for support-encoded masses. Its direct construction of the requested LP already resolves the task, so no additional extension of the finite-electorate result is needed.
Repair feedback: None required. The argument addresses the assigned exact continuous optimization problem and establishes its polynomial-time solvability.
⟨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.