Answer: Polynomial-time solvable.
Theorem 23 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateConsider any finite input preference set Λ ⊆IRp, any finite A ⊆IRp, and α ∈A. Then MRRDk A (α; VΛ) is finite for all k ∈{0, 1, 2, 3}. In addition, abbreviating VΛ to V, we have MRRD0 A (α; V) = max β∈A max{w · (β −α) : w ∈Vβ−ˆ A[β ≥A]}. MRRD1 A (α; V) = max β,γ∈A max{w·(β−α) : w ∈Vβ−γ[β ≥A ≥γ]}. MRRD2 A (α; V) = max β∈A max{w · (β −α) : w ∈Vβ−A[β ≥A]}.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite shared slate \(A\subseteq\mathbb{Q}^p\), rational comparison records \(\Lambda_t\subseteq\mathbb{Q}^p\) for each supported type \(t\), and rational masses \(\mu_t\ge 0\) summing to \(1\), find an alternative \(a\in A\) minimizing \(\sum_t\mu_t\,\mathrm{MRR}^{D_1}_A(a;V_{\Lambda_t})\), and return the exact minimum and all minimizing alternatives. Here \(V_{\Lambda_t}=\{w\in\mathbb{R}^p_{\ge0}:w\cdot\lambda\ge0\text{ for every }\lambda\in\Lambda_t\}\), and \(D^1_A(w)=\operatorname{Val}_A(w)-\operatorname{Wor}_A(w)\).
Given an explicitly listed nonempty shared slate \(A\subseteq\mathbb{Q}^p\), let \(m=|A|\) and \(p\ge1\); objective coordinates may have either sign, and higher utility is better.
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type supplies an explicitly listed finite set \(\Lambda_t\subseteq\mathbb{Q}^p\) of weak comparison constraints, defining \(V_{\Lambda_t}=\{w\in\mathbb{R}_{\ge0}^p:w\cdot\lambda\ge0\text{ for every }\lambda\in\Lambda_t\}\). Records need not compare alternatives from \(A\); empty records and cones consisting only of zero are allowed. Weights are not normalized.
Define \(\operatorname{Val}_A(w)=\max_{b\in A}w\cdot b\), \(\operatorname{Wor}_A(w)=\min_{b\in A}w\cdot b\), and \(D_A^1(w)=\operatorname{Val}_A(w)-\operatorname{Wor}_A(w)\).
For \(a\in A\), define \(r_A(a,w)=(\operatorname{Val}_A(w)-w\cdot a)/D_A^1(w)\) when \(D_A^1(w)>0\), and \(r_A(a,w)=0\) otherwise; define \(\mathrm{MRR}^{D_1}_A(a;V)=\sup_{w\in V}r_A(a,w)\).
The computational problem is to return the exact minimum of \(F(a)=\sum_{t=1}^{\tau}\mu_t\mathrm{MRR}^{D_1}_A(a;V_{\Lambda_t})\) over \(a\in A\), together with every minimizing alternative. Let \(q=\sum_t|\Lambda_t|\) and let \(L\) be the total binary input length; state running times in \(m,\tau,p,q,L\).
Is this exact mass-weighted minimization problem solvable in polynomial time in \(m,\tau,p,q,L\), or is it NP-hard?
For a single type and an explicitly listed finite slate, all alternatives' maximum range-relative regrets can be computed in polynomial time using linear programming. [Source](https://doi.org/10.3233/FAIA240884)
No result for exactly the mass-weighted problem above was located in the literature search.
The problem is solvable exactly in polynomial time in \(m,\tau,p,q,L\). An algorithm uses at most \(\tau m^2\) rational linear programs, followed by exact rational arithmetic to return the minimum and every minimizing alternative.
For \(m=1\), every regret is zero. The argument below also covers this case, empty records, and cones consisting only of zero.
Write \(V_t=V_{\Lambda_t}\). Since its defining inequalities are homogeneous, \(w\in V_t\) implies \(cw\in V_t\) for every \(c\ge 0\).
For each type \(t\) and each pair \(a,b\in A\), define the linear program
\( \displaystyle \begin{aligned} v_{t,a,b}=\max_w\quad &(b-a)\cdot w\\ \text{subject to}\quad &w_j\ge 0 &&(j=1,\ldots,p),\\ &\lambda\cdot w\ge 0 &&(\lambda\in\Lambda_t),\\ &0\le (b-d)\cdot w\le 1 &&(d\in A\setminus\{b\}). \end{aligned} \)
The final constraints require that \(b\) maximize utility and that the utility range be at most one.
Every such LP is feasible because \(w=0\) satisfies all constraints. Taking \(d=a\) shows that its objective lies between zero and one when \(a\ne b\); when \(a=b\), the objective is identically zero. Thus every LP has a finite optimum.
We use the standard theorem that a rational LP can be solved exactly in polynomial bit time, including when the feasible region is unbounded or has empty interior, provided its objective has a finite optimum. Polynomial-time LP algorithms and polynomial-size rational solutions are discussed in the [MIT algorithm notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) and [rational-output bounds](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf).
Claim. For every \(t\) and \(a\in A\),
\( \displaystyle \mathrm{MRR}^{D_1}_A(a;V_t)=\max_{b\in A}v_{t,a,b}. \)
Proof. Denote the left-hand side by \(M_t(a)\). Because \(a\in A\), the regret numerator lies between zero and the utility range whenever that range is positive. Together with the definition at zero range, this gives \(0\le r_A(a,w)\le 1\).
First fix \(b\in A\) and a feasible vector \(w\) for its LP. The constraints imply that \(b\) maximizes utility, so
\( \displaystyle D_A^1(w)=\max_{d\in A}(b-d)\cdot w\le 1. \)
If \(D_A^1(w)=0\), all alternatives have equal utility and \((b-a)\cdot w=0\le M_t(a)\).
If \(D_A^1(w)>0\), then
\( \displaystyle (b-a)\cdot w =D_A^1(w)\,r_A(a,w) \le r_A(a,w) \le M_t(a). \)
Here the first inequality uses both \(D_A^1(w)\le 1\) and \(r_A(a,w)\ge 0\); the last uses \(w\in V_t\). Consequently, \(v_{t,a,b}\le M_t(a)\), and therefore
\( \displaystyle \max_{b\in A}v_{t,a,b}\le M_t(a). \)
For the reverse inequality, take any \(w\in V_t\) with \(D_A^1(w)>0\). Because \(A\) is finite and nonempty, choose \(b\in A\) maximizing \(w\cdot b\). Put
\( \displaystyle \widehat w=\frac{w}{D_A^1(w)}. \)
Homogeneity gives \(\widehat w\in V_t\). For each \(d\in A\), maximality of \(b\) and the definition of the range give
\( \displaystyle 0\le(b-d)\cdot w\le D_A^1(w). \)
After division, these are exactly the LP’s range constraints. Thus \(\widehat w\) is feasible and
\( \displaystyle r_A(a,w) =\frac{(b-a)\cdot w}{D_A^1(w)} =(b-a)\cdot\widehat w \le v_{t,a,b} \le\max_{c\in A}v_{t,a,c}. \)
For weights with zero range, the regret is zero, whereas every LP optimum is nonnegative. Hence the same upper bound holds for all \(w\in V_t\). Taking the supremum proves the reverse inequality and the claim. \(\square\)
This proof uses no sign restriction on the alternatives’ coordinates. It also treats zero-range weights directly, without imposing a normalization on them.
The algorithm is:
Section 2 proves that these are precisely the required scores.
Every LP optimum is rational with polynomial encoding length. Multiplication by a rational mass preserves polynomial encoding length. Summing \(\tau\) rational terms also does: a common denominator can be chosen as the product of their denominators, whose bit length is the sum of their bit lengths. The corresponding numerator has polynomial bit length as well.
Thus scores and ties can be compared exactly by cross-multiplication of integers of polynomial bit length. Enumerating every minimizing alternative requires at most \(m\) output entries.
Let \(q_t=|\Lambda_t|\), so \(\sum_tq_t=q\). Each LP has:
Every coefficient has bit length \(O(L+1)\). A conservative bound on the total encoding length of one LP is
\( \displaystyle B_t=O\!\left((p+1)(p+q_t+m+1)(L+1)\right). \)
Let \(T_{\mathrm{LP}}(n,k,B)\) be a polynomial bit-time bound for exact rational LP with \(n\) variables, \(k\) inequalities, and encoding length \(B\). The total running time is
\( \displaystyle O\!\left( m^2\sum_{t=1}^{\tau} T_{\mathrm{LP}}\!\left(p,p+q_t+2(m-1),B_t\right) \right) +\operatorname{poly}(m,\tau,p,q,L), \)
where the additional polynomial covers LP construction, rational aggregation, and exact comparisons. In particular, this is
\( \displaystyle O\!\left(\tau m^2\,\operatorname{poly}(p+q+m+L)\right) \)
bit operations, after enlarging the fixed polynomial to include postprocessing.
The explicitly listed support permits processing each type separately, and the explicitly listed slate permits comparing all candidate scores. These two facts establish polynomial-time solvability of the exact mass-weighted problem.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The prover resolves the exact mass-weighted minimization problem as stated. The LP formulation and regret identity are correct, all permitted degeneracies are covered, and the exact arithmetic and running-time bounds are polynomial. I found no major or minor issues requiring repair.
The argument uses the explicitly listed slate and support exactly as required. It computes a separate regret for every type and candidate, then aggregates those regrets using the supplied masses.
The homogeneity assertion is correct: all constraints defining \(V_t\), including coordinate nonnegativity, are homogeneous weak inequalities. Therefore \(w\in V_t\) implies \(cw\in V_t\) for every \(c\geq0\). No normalization of weights or sign restriction on alternatives is introduced.
For fixed \(t,a,b\), the constraints
\[
0\leq(b-d)\cdot w\leq1
\]
for \(d\neq b\) have the stated interpretation:
The omitted constraint for \(d=b\) is automatically satisfied, since its expression is zero. Consequently, on the feasible region,
\[
D_A^1(w)=\max_{d\in A}(b-d)\cdot w\leq1.
\]
Feasibility follows from \(w=0\). If \(a\neq b\), the constraint indexed by \(d=a\) bounds the objective between zero and one. If \(a=b\), the objective is identically zero. Thus every LP is feasible and has bounded objective.
The invocation of exact rational linear programming is valid. Its relevant hypotheses—finite rational input, nonempty feasible polyhedron, and bounded objective—are all verified. An unbounded feasible region or empty interior does not invalidate this theorem. The cited notes discuss polynomial-time LP algorithms, degeneracy handling, and rational output bounds. [MIT algorithm notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html), [MIT LP notes, Sections 11–12](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf).
The prover correctly establishes \(0\leq r_A(a,w)\leq1\): when the range is positive, the numerator lies between zero and that range; when the range is zero, regret is defined to be zero.
For any LP-feasible \(w\), the selected \(b\) maximizes utility.
If the range is zero, every alternative has equal utility, so the LP objective is zero. Since \(M_t(a)\geq0\), the required bound follows.
If the range is positive, the identity
\[
(b-a)\cdot w=D_A^1(w)\,r_A(a,w)
\]
is correct. The subsequent inequality uses both the established range bound and nonnegativity of regret. Membership in \(V_t\) then permits comparison with the supremum defining \(M_t(a)\).
The resulting bound holds for every feasible vector, so taking the LP optimum and then the finite maximum over \(b\) is justified.
For every \(w\in V_t\) with positive range, a maximizing alternative \(b\) exists because \(A\) is finite and nonempty.
The scaling
\[
\widehat w=\frac{w}{D_A^1(w)}
\]
is well-defined and preserves membership in \(V_t\). Maximality of \(b\) and the definition of the range give exactly
\[
0\leq(b-d)\cdot w\leq D_A^1(w).
\]
Dividing by the positive range verifies every LP range constraint.
The normalized LP objective equals the original regret, so the stated upper bound by \(\max_c v_{t,a,c}\) follows. Zero-range weights satisfy that same bound because their regret is zero and all LP optima are nonnegative.
Taking the supremum is therefore valid. Both directions establish the claimed identity for every type and alternative, without assuming that a positive-range weight exists.
All explicitly permitted cases are handled:
There is no hidden domain or quantifier restriction.
The regret identity justifies every computed \(R_t(a)\). Consequently, the exact rational sum in Step 2 equals the requested \(F(a)\).
The encoding-length argument is sound. LP optima have polynomial rational encoding length; multiplication by an input mass preserves a polynomial bound. For a sum of \(\tau\) terms, the product of denominators has bit length equal to the sum of their bit lengths, hence remains polynomial. The corresponding numerator also has polynomial bit length.
Exact cross-multiplication therefore suffices for comparisons and tie detection. The algorithm returns both the exact minimum and every minimizing alternative.
No interchange of a supremum with the weighted sum is used or needed.
The LP dimensions are correctly counted: \(p\) variables and \(p+q_t+2(m-1)\) inequalities.
Input coordinates, record coefficients, and coordinate differences all have bit length \(O(L+1)\). The displayed bound \(B_t\) conservatively covers the constraint matrix, right-hand sides, and objective coefficients.
There are at most \(\tau m^2\) LP calls. Since \(q_t\leq q\), the detailed running-time expression yields the asserted polynomial bound in \(m,\tau,p,q,L\). LP construction, exact aggregation, comparisons, and output enumeration also fit within polynomial time.
The result is a polynomial bit-time algorithm; no strongly polynomial claim is made.
No mathematical repair or additional clarification is required. The output establishes the claimed polynomial-time classification for the full stated problem.
⟨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.