Answer: Exactly polynomial-time solvable in \(m,\tau,L\), with an optimal solution and its induced utility represented by finite kernel expressions with rational coefficients.
Theorem 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor sufficiently large μ (small ν), there is a concave utility function v over Y consistent with the data to within an er- ror of δ if and only if (DC) has an optimal solution (α, ¯α, s) with maxi,j∈N(αij + ¯αij) < μδ. In this case v can be evaluated as v(x) = min i∈N {vi + pi(x) −pi(xi)} (6) where, for each i ∈N, pi(x) = j∈N (¯αij −αij)[κ(xi, x) −κ(xj, x)]. (7) (Again, μ depends on δ.) According to the theorem, the pi can be evaluated given the α and ¯α from the dual solution. However, we also need to back out the vi’s from the primal.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(T\) of demand-record types with rational masses \(\mu_t>0\) summing to \(1\), chosen bundles \(x_t\), tariff costs \(c_{ts}\) for each supported bundle, and a kernel \(\kappa\), find values \(v_t\), feature-space slopes \(g_t\), multipliers \(\lambda_t\ge 1\), and slacks \(\epsilon_{ts},\bar\epsilon_{ts}\) minimizing \(\frac{\rho}{2}\sum_{t,s\in T}\mu_t\mu_s(\epsilon_{ts}^2+\bar\epsilon_{ts}^2)+\frac12\sum_{t\in T}\mu_t\|g_t\|_{\mathcal H_\kappa}^2\), subject to \(v_t-\langle g_t,\phi(x_t)\rangle+\epsilon_{ts}\ge v_s-\langle g_t,\phi(x_s)\rangle\) and \(\langle g_t,\phi(x_t)\rangle-\lambda_t c_{tt}+\bar\epsilon_{ts}\ge\langle g_t,\phi(x_s)\rangle-\lambda_t c_{ts}\) for every \(t,s\in T\); return the induced concave utility \(\hat u(x)=\min_{t\in T}\{v_t+\langle g_t,\phi(x)-\phi(x_t)\rangle\}\).
A society is given by its support: a list \(T\) of \(\tau\ge1\) demand-record types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type records a chosen bundle \(x_t\in\mathbb Q_+^m\), with \(m\ge1\), and costs \(c_{ts}\in\mathbb Q\) for every supported bundle. Costs are promised to be restrictions of strictly monotone tariffs \(p_t:\mathbb R_+^m\to\mathbb R\), with \(c_{ts}=p_t(x_s)\); the observed budget is \(c_{tt}\). Repeated chosen bundles are allowed.
Input also includes \(\rho\in\mathbb Q_{>0}\) and a positive-semidefinite kernel \(\kappa\), with feature map \(\phi\) into a Hilbert space \(\mathcal H_\kappa\). Its rational support Gram matrix is supplied, together with an exact rational kernel evaluator running in polynomial time in its description and argument lengths. Let \(L\) be the total binary input length.
Over \(v_t,\epsilon_{ts},\bar\epsilon_{ts}\in\mathbb R\), \(g_t\in\mathcal H_\kappa\), and \(\lambda_t\ge1\), minimize \(\frac{\rho}{2}\sum_{t,s\in T}\mu_t\mu_s(\epsilon_{ts}^2+\bar\epsilon_{ts}^2)+\frac12\sum_{t\in T}\mu_t\|g_t\|_{\mathcal H_\kappa}^2\).
For every \(t,s\in T\), require \(v_t-\langle g_t,\phi(x_t)\rangle+\epsilon_{ts}\ge v_s-\langle g_t,\phi(x_s)\rangle\) and \(\langle g_t,\phi(x_t)\rangle-\lambda_t c_{tt}+\bar\epsilon_{ts}\ge\langle g_t,\phi(x_s)\rangle-\lambda_t c_{ts}\).
Recover an exact optimum and its induced utility \(\hat u(x)=\min_{t\in T}\{v_t+\langle g_t,\phi(x)-\phi(x_t)\rangle\}\), represented by finite kernel expressions. Concavity is in feature space; global monotonicity is not an additional optimization constraint.
Is this mass-weighted utility-recovery problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
Discrete: [Lahaie (2010)](https://ebooks.iospress.nl/pdf/doi/10.3233/978-1-60750-606-5-439) gives a dual-slack characterization of approximate consistency and a kernel utility-recovery formula for the unweighted finite-observation formulation, for sufficiently large regularization weight.
Continuous-side nearest result: [Kozlov–Tarasov–Khachiyan (1980)](https://www.mathnet.ru/eng/zvmmf5189) establish polynomial-time exact solution of rational convex quadratic programs. No treatment of exactly the mass-weighted utility-recovery problem was verified.
The problem is solvable exactly in time polynomial in \(m,\tau,L\). This holds for every rational \(\rho>0\), including singular support Gram matrices and repeated chosen bundles.
The proof reduces the Hilbert-space problem to a rational convex quadratic program of polynomial encoding length, then applies the exact polynomial-time quadratic-programming theorem.
Index the support by \(T=\{1,\ldots,\tau\}\), and write \(K_{rs}=\kappa(x_r,x_s)=\langle\phi(x_r),\phi(x_s)\rangle\). By hypothesis, \(K\) is rational and positive semidefinite.
Let \(S=\operatorname{span}\{\phi(x_r):r\in T\}\). This finite-dimensional subspace of \(\mathcal H_\kappa\) is closed, so it has an orthogonal projection \(P_S\).
For any feasible solution, decompose \(g_t=P_Sg_t+h_t\), where \(h_t\perp S\). For every supported bundle \(x_s\),
\(\langle g_t,\phi(x_s)\rangle=\langle P_Sg_t,\phi(x_s)\rangle.\)
Thus replacing each \(g_t\) by \(P_Sg_t\) preserves every constraint. Orthogonality also gives
\(\|g_t\|_{\mathcal H_\kappa}^2=\|P_Sg_t\|_{\mathcal H_\kappa}^2+\|h_t\|_{\mathcal H_\kappa}^2.\)
Consequently, this replacement weakly decreases the objective. Because \(\mu_t>0\), it strictly decreases the objective whenever any \(h_t\ne0\).
It therefore suffices to optimize over \(g_t\in S\). Every such vector has a representation
\(g_t=\sum_{r=1}^{\tau}a_{tr}\phi(x_r)\)
with real coefficients \(a_{tr}\). No linear independence assumption is needed. Writing \(a_t=(a_{t1},\ldots,a_{t\tau})^{\mathsf T}\), we obtain
\(\langle g_t,\phi(x_s)\rangle=\sum_{r=1}^{\tau}a_{tr}K_{rs},\qquad \|g_t\|_{\mathcal H_\kappa}^2=a_t^{\mathsf T}Ka_t.\)
Substitution produces the finite-dimensional objective
\(F(a,v,\lambda,\epsilon,\bar\epsilon)=\frac{\rho}{2}\sum_{t,s=1}^{\tau}\mu_t\mu_s(\epsilon_{ts}^2+\bar\epsilon_{ts}^2)+\frac12\sum_{t=1}^{\tau}\mu_t a_t^{\mathsf T}Ka_t.\)
For every \(t,s\in T\), its constraints are
\(v_t-v_s+\epsilon_{ts}-\sum_{r=1}^{\tau}a_{tr}(K_{rt}-K_{rs})\ge0,\)
\(\sum_{r=1}^{\tau}a_{tr}(K_{rt}-K_{rs})-\lambda_t(c_{tt}-c_{ts})+\bar\epsilon_{ts}\ge0,\)
together with \(\lambda_t\ge1\).
We may additionally impose \(v_1=0\): subtracting \(v_1\) from every \(v_t\) preserves all constraints and the objective.
There are \(3\tau^2+2\tau\) scalar variables and \(2\tau^2+\tau\) inequalities, plus this normalization equality.
All coefficients are rational. The objective Hessian is block diagonal:
Since \(K\) is positive semidefinite and all masses and \(\rho\) are positive, this Hessian is positive semidefinite. The resulting problem is therefore a rational convex quadratic program.
To verify equivalence, let \(I_{\mathcal H}\) and \(I_Q\) denote the respective infima. Every feasible coefficient vector defines a feasible Hilbert-space solution of identical objective value, so \(I_{\mathcal H}\le I_Q\). Conversely, projecting any feasible Hilbert-space solution onto \(S\), representing the projected vectors by coefficients, and normalizing \(v\) produces a feasible quadratic-program solution of no larger objective value. Hence \(I_Q\le I_{\mathcal H}\), and the infima coincide.
The quadratic program is feasible. An explicit rational feasible point is
\(a_{tr}=0,\quad v_t=0,\quad \lambda_t=1,\quad \epsilon_{ts}=0,\quad \bar\epsilon_{ts}=\max\{c_{tt}-c_{ts},0\}.\)
Indeed, every first inequality holds with equality, and every second inequality reduces to \(\bar\epsilon_{ts}\ge c_{tt}-c_{ts}\).
The objective is nonnegative, because its slack terms have positive coefficients and \(a_t^{\mathsf T}Ka_t\ge0\). Thus it is bounded below on its nonempty feasible polyhedron.
We now use the following established result:
Exact convex quadratic-programming theorem. Given rational data defining a quadratic objective with positive-semidefinite Hessian and finitely many linear constraints, feasibility and boundedness can be decided in polynomial time. If feasible and bounded below, an exact rational minimizer and the exact minimum value can be computed in polynomial time in the binary encoding length. This is the theorem of [Kozlov–Tarasov–Khachiyan (1980)](https://www.mathnet.ru/eng/zvmmf5189); their definition of exact solution includes an attaining point.
Their integer-data formulation applies to rational data by clearing denominators. Multiplying the objective by a positive common denominator preserves its minimizers and positive semidefiniteness; clearing each constraint’s denominators by a positive multiplier preserves its feasible set. These operations increase encoding length only polynomially.
All hypotheses have now been checked: our program has rational data, a positive-semidefinite Hessian, a nonempty feasible set, and an objective bounded below. The theorem therefore supplies an exact rational optimum
\((a^*,v^*,\lambda^*,\epsilon^*,\bar\epsilon^*).\)
Defining \(g_t^*=\sum_r a_{tr}^*\phi(x_r)\) gives an exact optimum of the original problem, by the equivalence proved above. In particular, possible unbounded directions in the coefficient, utility-level, or multiplier variables do not obstruct attainment or exact recovery.
Every coefficient of the quadratic program is obtained from input rationals using a fixed number of additions and multiplications, such as \(\rho\mu_t\mu_s\), \(\mu_tK_{rs}\), \(K_{rt}-K_{rs}\), and \(c_{tt}-c_{ts}\). Each therefore has binary length polynomial in \(L\).
The numbers of variables, constraints, and matrix entries are polynomial in \(\tau\). Consequently, the entire quadratic program has encoding length polynomial in \(\tau,L\), and can be constructed in polynomial time. Exact quadratic programming then takes polynomial time in that length.
This argument never expands a mass into multiple observations and never enumerates unsupported types. Small binary-encoded masses affect coefficient bit lengths, rather than the number of variables. Likewise, singularity of \(K\) requires neither an inverse nor a square-root factorization.
Together with the input bundle descriptions, this establishes the requested polynomial bound in \(m,\tau,L\).
The recovered vectors are represented by the finite expressions
\(g_t^*=\sum_{r=1}^{\tau}a_{tr}^*\phi(x_r).\)
Their induced utility is exactly
\(\hat u(x)=\min_{1\le t\le\tau}\left\{v_t^*+\sum_{r=1}^{\tau}a_{tr}^*\bigl(\kappa(x_r,x)-K_{rt}\bigr)\right\}.\)
All stored coefficients are rational and have polynomial total output length, because the exact optimization algorithm runs in polynomial time.
For a rational query bundle \(x\), compute the \(\tau\) kernel values \(\kappa(x_r,x)\), reuse them across the \(\tau\) expressions, and take their minimum. The promised exact polynomial-time evaluator and polynomially many rational arithmetic operations give exact evaluation in time polynomial in \(m,\tau,L\) and the query’s binary length.
Finally, define on feature space
\(U(y)=\min_t\{v_t^*+\langle g_t^*,y-\phi(x_t)\rangle\}.\)
Writing each expression inside the minimum as \(A_t(y)\), its affinity implies, for \(y,z\in\mathcal H_\kappa\) and \(\theta\in[0,1]\),
\(U(\theta y+(1-\theta)z)=\min_t\{\theta A_t(y)+(1-\theta)A_t(z)\}\ge\theta\min_t A_t(y)+(1-\theta)\min_t A_t(z).\)
Thus \(U\) is concave in feature space and \(\hat u=U\circ\phi\), as required.
The tariff promise adds no optimization constraints beyond the supplied costs. The argument also requires no large-regularization assumption: every rational \(\rho>0\) is covered.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the task. The reduction, exact optimization claim, and utility representation are correct. No major or minor mathematical issues were found.
The space \(S=\operatorname{span}\{\phi(x_r):r\in T\}\) is finite dimensional and therefore closed. The orthogonal projection used in Section 1 exists.
Every constraint depends on \(g_t\) only through inner products with supported feature vectors. Projection onto \(S\) preserves these inner products and hence feasibility. The stated norm decomposition is correct, and the positive masses ensure a strict objective decrease whenever a nonzero orthogonal component is removed.
This establishes the claimed reduction without assuming that the support feature vectors are linearly independent. Although projection can change the utility away from the support, the task requires recovery of an optimum and its induced utility; it does not require preserving the utility of every initial feasible solution.
Every vector in \(S\) has the stated coefficient representation. Both identities
\[
\langle g_t,\phi(x_s)\rangle=\sum_r a_{tr}K_{rs},
\qquad
\|g_t\|_{\mathcal H_\kappa}^2=a_t^{\mathsf T}Ka_t
\]
follow directly from the Gram matrix definition.
Nonuniqueness of coefficients when \(K\) is singular causes no inconsistency: the optimization uses precisely the inner products and norms represented by these formulas.
The substituted objective has the correct mass factors and factors of one half. Its Hessian blocks are correctly identified as \(\mu_tK\) and the scalar entries \(\rho\mu_t\mu_s\), with zero blocks for \(v\) and \(\lambda\). Thus the Hessian is positive semidefinite.
Both displayed families of inequalities have the correct signs. In particular, the second original constraint rearranges to
\[
\sum_r a_{tr}(K_{rt}-K_{rs})
-\lambda_t(c_{tt}-c_{ts})+\bar\epsilon_{ts}\ge0.
\]
Translating every \(v_t\) by the same constant preserves all constraints and the objective, so imposing \(v_1=0\) is legitimate.
The counts are correct: there are \(3\tau^2+2\tau\) scalar variables and \(2\tau^2+\tau\) inequalities before adding the normalization equality. An equality is permitted in the cited framework through its routine representation as two linear inequalities.
The two comparisons of infima are justified. A feasible coefficient solution defines a feasible Hilbert-space solution with identical objective value. Conversely, projection, coefficient representation, and normalization produce a feasible quadratic-program solution with no greater objective value.
Consequently, once an attaining optimum of the quadratic program is obtained, its represented Hilbert-space solution attains the original infimum. There is no circular reliance on attainment in the preceding reduction.
The proposed rational feasible point satisfies \(\lambda_t\ge1\) and \(v_1=0\). The first constraints become equalities, and the second become
\[
\max\{c_{tt}-c_{ts},0\}\ge c_{tt}-c_{ts},
\]
which holds for every pair, including negative cost differences.
Every objective term is nonnegative, so the objective is bounded below. The reasoning does not incorrectly infer compactness from boundedness.
The stated theorem matches the cited source. The original paper defines exact solution to include feasibility determination, lower-boundedness determination, the exact optimal value, and an attaining point. It treats positive-semidefinite integer quadratic data and establishes polynomial time in binary input length. Its rational optimal-point discussion supports the rational-output claim. See the [original paper, especially pages 1320–1323](https://www.mathnet.ru/php/getFT.phtml?jrnid=zvmmf&option_lang=eng&paperid=5189&what=fullt).
All required hypotheses are verified in the output. Positive denominator clearing preserves feasibility, minimizers, and positive semidefiniteness. The claimed polynomial encoding increase is valid. Neither singularity nor unbounded feasible directions invalidate this application.
Each constructed coefficient involves a bounded number of operations on input rationals, so its binary length is polynomial in \(L\). The number of coefficients is polynomial in \(\tau\), including a dense encoding of the quadratic objective.
Denominator clearing also preserves polynomial encoding length: the bit length of a common denominator is bounded by the sum of the constituent denominator lengths. The exact optimization theorem therefore applies to a program of polynomial total size.
The argument correctly treats masses as binary-encoded weights. It does not expand them into observations or enumerate unsupported types.
Substitution of the recovered coefficient expressions gives exactly the displayed kernel formula for \(\hat u\). The finite representation stores polynomially many rational coefficients of polynomial total length.
For rational query bundles, the promised evaluator supplies the needed kernel values in polynomial time. The subsequent rational arithmetic and finite minimum preserve the stated polynomial evaluation bound.
The feature-space concavity calculation is correct for every \(y,z\in\mathcal H_\kappa\) and \(\theta\in[0,1]\). It establishes precisely the concavity required by the task. No additional global monotonicity condition or large-\(\rho\) assumption is needed.
The cases \(\tau=1\), repeated bundles, and singular or zero Gram matrices are all covered by the written argument. No repair or additional clarification is necessary.
⟨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.