| paper | d4-conf-ecai-2010-0070 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
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. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
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 cohort of many households with a common underlying utility faces different nonlinear tariffs and chooses bundles. Each type records a household's tariff and choice context; its mass is its population share. Fit one population-level concave kernel utility by minimizing expected pairwise consistency error plus mass-weighted regularization, using kernel values on the supported bundles.
The mass-weighted objective targets average fit, so it does not retain Theorem 3's uniform consistency condition for every observed record; rare types may receive less accurate fits.
fatal: False
The mirror covers the concave feature-space fitting method in Theorem 3. It leaves the linear kernel method, Afriat's background result, and the empirical comparisons as separate questions.
The strongest case I see is a high-multiplicity mirror of the paper’s concave kernel fitting method. Picture a large, narrowly defined consumer cohort in a tariff study: many households share the same underlying preferences, while facing different nonlinear tariffs and choosing different bundles. A type is a complete observed tariff-and-choice record, including its chosen bundle and the recorded prices of the cohort’s observed bundles. Its mass \(\mu_t\) is the fraction of households with that record. A study might have millions of households but only hundreds or thousands of distinct records.
The anchor is Theorem 3, proved in this paper using strong duality and the KKT conditions. It says that, for sufficiently large regularization parameter \(\eta\) (equivalently, small \(\nu=1/\eta\)), a concave utility in feature space that is consistent with the observations within error \(\delta\) exists if and only if the dual program \((DC)\) has an optimal solution \((\alpha,\bar\alpha,s)\) with \(\max_{i,j}(\alpha_{ij}+\bar\alpha_{ij})<\eta\delta\). The dual maximizes
\[
\sum_i s_i-\frac{\nu}{2}\|\alpha\|_2^2-\frac{\nu}{2}\|\bar\alpha\|_2^2
-\frac12\sum_i\left\|\sum_j(\bar\alpha_{ij}-\alpha_{ij})(\phi(x_i)-\phi(x_j))\right\|^2
\]
over nonnegative \(\alpha,\bar\alpha,s\), subject to
\[
s_i=\sum_j\bar\alpha_{ij}(c_{ii}-c_{ij}),\qquad
\sum_j\alpha_{ij}=\sum_j\alpha_{ji}.
\]
When the threshold holds, the fitted utility is
\[
v(x)=\min_i\{v_i+p_i(x)-p_i(x_i)\},\qquad
p_i(x)=\sum_j(\bar\alpha_{ij}-\alpha_{ij})[\kappa(x_i,x)-\kappa(x_j,x)].
\]
The primal values \(v_i\) can be recovered using the KKT conditions. This is a computational anchor: the paper defines this fit and evaluates it empirically. The paper has no named NP-hardness, FPT, or P-completeness result, so there is no hardness anchor to use.
Here is the corresponding continuous problem. An instance gives a finite support \(T\), rational masses \(\mu_t>0\) summing to \(1\), a chosen bundle \(x_t\) for each type, and the cost matrix \(c_{ts}\), where \(c_{ts}\) is the price type \(t\)’s tariff assigns to type \(s\)’s observed bundle. It also gives a kernel \(\kappa\) whose values can be computed from the input. Find a population-level concave kernel utility fit, represented by values \(v_t\), feature-space slopes \(g_t\), positive multipliers \(\lambda_t\ge1\), and slacks \(\epsilon_{ts},\bar\epsilon_{ts}\), minimizing
\[
\frac{\rho}{2}\sum_{t,s}\mu_t\mu_s(\epsilon_{ts}^2+\bar\epsilon_{ts}^2)
+\frac12\sum_t\mu_t\|g_t\|_{\mathcal H_\kappa}^2
\]
subject, for every \(t,s\in T\), to
\[
v_t-\langle g_t,\phi(x_t)\rangle+\epsilon_{ts}
\ge v_s-\langle g_t,\phi(x_s)\rangle,
\]
\[
\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}.
\]
The solution includes the utility
\[
\hat u(x)=\min_{t\in T}\{v_t+\langle g_t,\phi(x)-\phi(x_t)\rangle\}.
\]
The masses weight the population’s pairwise consistency error and the per-capita regularization. This is the mass-normalized version of the paper’s fitting criterion; Theorem 3 motivates the utility class and kernel computation, while the weighted objective is the population co-modification.
I expect this problem to be tractable, in Class A: it is a convex quadratic program with \(O(\tau^2)\) comparison constraints, and the kernel trick expresses its feature-space terms using kernel values on the supported bundles. A prover could establish the precise bit-complexity and approximation guarantees for a specified kernel family. Further questions include whether the estimate generalizes to consumers outside the observed support, how much price information can be omitted, and whether a useful version can accommodate heterogeneous preferences.
This case covers Theorem 3’s concave feature-space fitting problem. It does not claim to mirror the paper’s other kernel method, its Afriat background theorem, or its experiments as separate problems.
The soft spot is the shared-preference assumption: the paper reconstructs one agent’s utility from observations across price situations, while this scenario pools observations from many people. A tightly defined cohort under a standardized tariff study makes that assumption plausible, and positive affine transformations of one common utility leave choices unchanged. If preferences vary substantially across the cohort, the mirror would need a population of utility types or another heterogeneity model, which Theorem 3 does not establish.
The strongest objection is that Theorem 3 is not a complexity result of the kind ChoCo is charting. It characterizes when the paper’s regularized concave fit has a solution, through an optimal solution to a dual quadratic program. The paper gives no worst case complexity bound for that problem; its runtime evidence is empirical. The theorem can anchor a question about a fitting method, but it does not anchor a complexity landscape result.
The tariff cohort is a coherent attempt to supply a population. Suppose many households share one utility and face a finite menu of tariffs. If the mirror preserves Theorem 3’s consistency condition, every positive mass type still imposes its constraints. The masses then affect only which types occur, and repeated households with the same tariff and bundle add no new constraints. The computation is the same kernel quadratic program on the support of observations. If instead the objective weights slack by \(\mu_t\mu_s\), as proposed, rare types can be fitted poorly at little cost. That is a population average fitting objective, distinct from the theorem’s condition that observations be consistent within the stated error.
Heterogeneous preferences offer a stronger population interpretation, but a single shared utility no longer represents the cohort. Giving each preference type its own utility changes the estimation problem and leaves Theorem 3 as its anchor only by analogy. In either version, the population either compresses repeated observations or motivates a new weighted learning objective; it does not turn the paper’s theorem into a ChoCo style computational result.
This is a qualified negative case, not a demonstration that no useful mirror can exist. A mass weighted fitting method could be useful for econometric estimation, and the homogeneous tariff cohort is plausible. I would argue against prioritizing it as a continuization mirror of this paper’s results, while conceding that the broader claim that no scenario could make it worthwhile is weak.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.