Answer: Polynomial-time solvable
Corollary 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateWe can solve for an outcome under DBRlog in polynomial time. Of course, we can also use the hill-climbing algorithm de- scribed in the previous section to the transformed instance and then transform it back to the multiplicative model to ob- tain a (possibly suboptimal) solution. Experiments We generated three classes of voting profiles and compare the different algorithms’ performances in terms of running time, penalty (LP’s objective), and the distance between the aggregated result and the ground truth (if there is one). For the first class of voting profile (uniform), each vote is generated as follows.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite activity set \(A\), oriented pair set \(E\), and a rational distribution \(\mu\) over \(\tau\) complete report types \(\theta\), each with rational log-reports \(r_\theta^{ab}\) for \((a,b)\in E\), compute normalized qualities \(q\) minimizing \(\sum_\theta \mu_\theta\sum_{(a,b)\in E}|q_a-q_b-r_\theta^{ab}|\), and return the induced consistent tradeoffs \(t^{ab}=e^{q_a-q_b}\).
Let \(A\) be a nonempty activity set of size \(m\), with a designated activity \(a_0\). Let \(E\) contain exactly one orientation of each unordered pair of distinct activities, and no loops.
A society is given by its support: a list of \(\tau\) complete report types with positive binary-rational masses \(\mu_\theta\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type specifies \(r_\theta^{ab}\in\mathbb Q\) for every \((a,b)\in E\), interpreted as the natural logarithm of a positive ideal tradeoff. Reports need not be consistent. Let \(L\) be the total binary input length.
Compute a minimizer over \(q\in\mathbb R^A\), normalized by \(q_{a_0}=0\), of \(\sum_\theta\mu_\theta\sum_{(a,b)\in E}|q_a-q_b-r_\theta^{ab}|\). Any minimizer is acceptable.
Return exact rational qualities and the induced tradeoffs \(t^{ab}=\exp(q_a-q_b)\), represented symbolically by their rational exponents. Extend to reverse pairs by reciprocals and set \(t^{aa}=1\); consistency means \(t^{ab}t^{bc}=t^{ac}\) for all activities.
Is this exact optimization problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a finite list of equally weighted voters, computing an outcome minimizing total logarithmic tradeoff distance is known to be polynomial-time solvable ([source](https://www.cs.cmu.edu/~conitzer/tradeoffsAAAI16.pdf)).
No separate result settling the exact rational-support distribution problem was located in the literature search.
The problem is solvable exactly in polynomial time in \(m,\tau,L\). Rational support masses enter directly as objective coefficients in a rational linear program.
The supplied paper gives the corresponding linear program for equally weighted voters and the logarithmic transformation connecting qualities to consistent tradeoffs. The proof below handles rational support masses and exact binary encoding explicitly. [Conitzer et al., *Rules for Choosing Societal Tradeoffs*](https://www.cs.cmu.edu/~conitzer/tradeoffsAAAI16.pdf).
If \(m=1\), return \(q_{a_0}=0\) and \(t^{a_0a_0}=1\). The objective is an empty sum, so this is optimal. Henceforth suppose \(m\geq 2\).
Write \(s=|E|=\binom{m}{2}\), and define
\(F(q)=\sum_{\theta=1}^{\tau}\mu_\theta\sum_{(a,b)\in E}|q_a-q_b-r_\theta^{ab}|.\)
The normalized vector \(q=0\) has rational objective value
\(C=F(0)=\sum_{\theta=1}^{\tau}\mu_\theta\sum_{(a,b)\in E}|r_\theta^{ab}|.\)
Introduce a real variable \(z_\theta^{ab}\) for each report type and each oriented pair. Eliminate \(q_{a_0}\) by substituting zero. Consider the linear program minimizing
\(G(z)=\sum_{\theta=1}^{\tau}\mu_\theta\sum_{(a,b)\in E}z_\theta^{ab},\)
subject to the following inequalities for every \(\theta\) and \((a,b)\in E\):
\(z_\theta^{ab}\geq q_a-q_b-r_\theta^{ab},\)
\(z_\theta^{ab}\geq -q_a+q_b+r_\theta^{ab},\)
and the additional inequality
\(G(z)\leq C.\)
The first two inequalities are equivalent to
\(z_\theta^{ab}\geq |q_a-q_b-r_\theta^{ab}|.\)
Consequently, every feasible point satisfies \(F(q)\leq G(z)\leq C\). Conversely, every normalized \(q\) with \(F(q)\leq C\) has a feasible lift obtained by setting
\(z_\theta^{ab}=|q_a-q_b-r_\theta^{ab}|,\)
whose objective is exactly \(F(q)\).
The additional bound \(G(z)\leq C\) is harmless: a vector with \(F(q)>C\) is worse than \(q=0\). Thus, once attainment is established, the linear program and the original problem have the same minimum, and the quality coordinates of any optimal LP solution minimize \(F\).
We prove that the LP feasible set is nonempty and compact.
Nonemptiness follows by taking \(q=0\) and \(z_\theta^{ab}=|r_\theta^{ab}|\).
For each \(a\neq a_0\), let \(e_a\) be the unique orientation in \(E\) of the pair \(\{a,a_0\}\), and write \(r_\theta^{e_a}\) for its report. Since \(q_{a_0}=0\), the reverse triangle inequality gives, regardless of orientation,
\(|q_a-q_{a_0}-r_\theta^{e_a}|\geq |q_a|-|r_\theta^{e_a}|\)
when \(e_a=(a,a_0)\), and
\(|q_{a_0}-q_a-r_\theta^{e_a}|\geq |q_a|-|r_\theta^{e_a}|\)
when \(e_a=(a_0,a)\).
Keep only these incident-edge terms in \(F(q)\). Using \(\sum_\theta\mu_\theta=1\), we obtain
\(F(q)\geq \sum_{a\neq a_0}|q_a|-R_0,\)
where
\(R_0=\sum_{a\neq a_0}\sum_{\theta=1}^{\tau}\mu_\theta|r_\theta^{e_a}|\leq C.\)
Every feasible LP point therefore satisfies
\(\sum_{a\neq a_0}|q_a|\leq F(q)+R_0\leq 2C.\)
Also, the absolute-value constraints imply \(z_\theta^{ab}\geq 0\). Because all masses are strictly positive and \(G(z)\leq C\),
\(0\leq z_\theta^{ab}\leq C/\mu_\theta.\)
Hence every coordinate is bounded. The feasible set is closed because it is defined by finitely many non-strict linear inequalities. It is therefore compact, and the continuous linear objective attains a minimum.
Let \((q^*,z^*)\) be an LP minimizer. If some normalized \(q\) satisfied \(F(q)<F(q^*)\), then \(F(q)<F(q^*)\leq G(z^*)\leq C\). Its canonical lift would be feasible with objective \(F(q)<G(z^*)\), a contradiction. Thus \(q^*\) is a global minimizer of the original objective.
We use the standard exact rational linear-programming theorem: a linear program with binary-encoded rational coefficients can be solved in time polynomial in its encoding length; when its feasible set is nonempty and its objective has a finite minimum, an exact rational optimal solution can be returned. Polynomial-time solvability originates with [Khachiyan’s linear-programming theorem](https://www.mathnet.ru/eng/dan42319).
Here all hypotheses hold:
The coefficient data consist of input rationals, signs and zeros, and the computed rational \(C\). Computing \(C\) requires polynomially many rational operations with polynomial bit length: each summand is a product of input rationals, and a common denominator for their sum can be taken as the product of the summand denominators. The binary length of that product is at most the sum of their binary lengths, which is polynomial in \(m,\tau,L\). Repetition of masses across pairs also increases the LP encoding length only polynomially.
For completeness, exact output has polynomial encoding length independently of any numerical approximation argument. A linear objective on a nonempty compact polytope has an optimal vertex. At a vertex in \(D\) variables, \(D\) linearly independent tight constraints determine the coordinates. Clear denominators in those equations, obtaining an integer system whose entries have polynomial bit length. If every entry, including the right-hand side, has absolute value at most \(2^K\), Cramer’s rule expresses each coordinate as a ratio of determinants bounded in absolute value by
\(D!\,2^{KD}.\)
Their binary lengths are therefore at most \(KD+O(D\log D)\), which is polynomial in \(m,\tau,L\).
Applying an exact polynomial-time LP algorithm consequently returns rational qualities \(q^*\) in polynomial time.
For every ordered pair of activities, compute the exact rational exponent
\(x^{ab}=q_a^*-q_b^*\)
and return \(t^{ab}=\exp(x^{ab})\) symbolically through \(x^{ab}\). Rational subtraction and the output of all \(m^2\) exponents take polynomial time.
For all activities \(a,b,c\),
\(x^{ab}+x^{bc}=(q_a^*-q_b^*)+(q_b^*-q_c^*)=q_a^*-q_c^*=x^{ac}.\)
Therefore,
\(t^{ab}t^{bc}=\exp(x^{ab}+x^{bc})=\exp(x^{ac})=t^{ac}.\)
Furthermore, \(x^{ba}=-x^{ab}\) and \(x^{aa}=0\), so reverse tradeoffs are reciprocals and \(t^{aa}=1\).
This completes the exact polynomial-time algorithm and its correctness proof.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The argument establishes an exact polynomial-time algorithm for the stated rational-support encoding. No major or minor mathematical issues were found.
The proof addresses the actual support representation: it uses \(\tau\) report types with rational objective weights \(\mu_\theta\). It does not expand these weights into a potentially exponentially large electorate.
For \(m=1\), there are no report edges, the objective is zero, and normalization determines the sole quality. Returning \(q_{a_0}=0\) and \(t^{a_0a_0}=1\) is correct.
For each report and edge, the two stated inequalities are exactly equivalent to
\(z_\theta^{ab}\geq |q_a-q_b-r_\theta^{ab}|\).
They also imply nonnegativity of every auxiliary variable.
Because the masses are positive, summing these inequalities gives \(F(q)\leq G(z)\). The canonical lift defined in the proof achieves equality.
The cutoff \(G(z)\leq C\), where \(C=F(0)\), is legitimate. The normalized zero vector provides a feasible benchmark, and any quality vector with objective exceeding \(C\) cannot be optimal. Every quality vector with objective at most \(C\) retains its canonical feasible lift.
Thus the formulation preserves the relevant optimization problem. No consistency assumptions on the reports are used.
The proposed feasible point \(q=0\), \(z_\theta^{ab}=|r_\theta^{ab}|\) satisfies every constraint, including the cutoff with equality.
The bounds on qualities are correct for both possible orientations of each edge incident to \(a_0\). Keeping these distinct incident-edge terms and applying the reverse triangle inequality yields
\(F(q)\geq \sum_{a\neq a_0}|q_a|-R_0\).
The normalization of the masses is used correctly in obtaining coefficient one on each \(|q_a|\).
Since \(R_0\) is a subsum of the nonnegative summands defining \(C\), the assertion \(R_0\leq C\) is valid. Consequently every feasible point satisfies
\(\sum_{a\neq a_0}|q_a|\leq 2C\).
The auxiliary-variable bound
\(0\leq z_\theta^{ab}\leq C/\mu_\theta\)
also follows correctly. Strict positivity of each mass is essential here and is expressly supplied by the task.
The feasible set is therefore nonempty, closed, and bounded in finite-dimensional space. Compactness and attainment of the linear objective follow. This argument also covers \(C=0\); there is no division by \(C\).
Finally, the contradiction argument correctly shows that the quality coordinates of any LP minimizer globally minimize \(F\). It does not require an unstated assumption that its auxiliary variables already equal their absolute-value lower bounds.
The invoked exact rational LP theorem is a standard valid theorem, stated with the relevant encoding and output requirements. Its hypotheses hold here:
The analysis of the computed coefficient \(C\) is sound. Products of input rationals and sums over polynomially many terms have polynomial encoding length under the denominator bound given in the proof. Repeated appearances of a mass across edges cause only polynomial growth in the explicit LP representation.
The separate output-length argument is also valid. A nonempty compact polytope has an optimal vertex, and at a vertex in \(D\) variables there are \(D\) linearly independent tight constraint rows. This remains true when the polytope has lower affine dimension.
Clearing denominators produces an integer system of polynomial entry length. The determinant bound \(D!\,2^{KD}\) applies to both the coefficient determinant and the determinants used for coordinate numerators. The denominator determinant is nonzero by linear independence. Thus rational vertex coordinates admit polynomial-length encodings.
The proof correctly invokes an exact polynomial-time LP algorithm for computation; it does not mistake the existence of short rational coordinates for an algorithm to find them.
Subtracting rational quality coordinates produces exact rational exponents of polynomial encoding length. Returning all \(m^2\) such exponents requires polynomial time and output space.
The displayed telescoping identity establishes consistency for every triple of activities, including repeated activities. The identities \(x^{ba}=-x^{ab}\) and \(x^{aa}=0\) correctly establish reciprocal reverse tradeoffs and unit diagonal tradeoffs.
Symbolic exponent representation matches the task exactly; numerical computation of exponentials is unnecessary.
The cited [Conitzer et al. paper](https://www.cs.cmu.edu/~conitzer/tradeoffsAAAI16.pdf) contains the additive LP formulation and the logarithmic transformation described by the prover. The [Khachiyan reference](https://www.mathnet.ru/eng/dan42319) is correctly identified as the historical polynomial-time linear-programming result. The prover explicitly states the exact rational theorem it uses and verifies its hypotheses.
No repair or additional clarification is required. The result establishes polynomial-time solvability for the specified encoding.
⟨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.