| paper | d4-conf-ecai-2023-0458 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: Deciding whether the optimum is at most \(q\) is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions, already for \(m=2\) and \(\tau=1\). Exact value computation and finding a minimizing recommendation are NP-hard. For fixed \(p\), the problem is polynomial-time solvable. The threshold problem is NP-hard under Turing reductions, and under many-one reductions if and only if \(\mathrm{NP}=\mathrm{coNP}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite set \(A\) of rational objective vectors and a finite support of user-profile types \(t\), each with rational mass \(\mu_t\), consistent preference constraints \(\Lambda_t\), and a compact rational rescaling range \(R_t\subset\mathbb{R}^p_{>0}\), compute a recommendation \(a_t\in A\) for each type minimizing \(\sum_t\mu_t\max_{\sigma\in R_t}\mathrm{MR}(H_\sigma(a_t),H_\sigma(A);W^1_{H_\sigma(\Lambda_t)})\).
A high-volume recommendation service is represented by a rational distribution \(\mu\) over complete user-profile types; each type receives one recommendation from the shared menu \(A\), and the service minimizes average per-type worst-case regret over each type’s rescaling range.
The policy separates by type, so masses affect the reported aggregate regret but not the recommendations; this makes the population calculation largely a batch application of Theorem 3.
fatal: False
The mirror uses Theorem 3 to compute each type’s scale-robust recommendation score and aggregate those scores by mass; it leaves the paper’s ratio characterizations, absolute bounds, asymptotic analysis, and bounded-preference-model results outside the mirror.
The strongest honest case is a high-volume recommendation service that must choose a product or policy for each recurring user cohort. A cohort’s members face the same finite alternatives \(A\), have the same elicited preference constraints \(\Lambda_t\), and use the same plausible range \(R_t\) of objective rescalings. These are complete types for this problem: members are indistinguishable in the data used to calculate regret. If there are \(N\) users but only \(\tau\) such profiles, the society is \(\mu\) over those \(\tau\) types, where \(\mu_t\) is the fraction of users in type \(t\). Large \(N\) and modest \(\tau\) are plausible for a platform with many users but recurring preference profiles.
Lead mirror — population scale-robust recommendation. The input is a finite alternative set \(A\) of rational objective vectors; a finite support of types with rational masses \(\mu_t\) summing to one; and, for each type, consistent preference constraints \(\Lambda_t\) and a compact, rationally represented rescaling range \(R_t\subset\mathbb R^p_{>0}\). Choose one recommendation \(a_t\in A\) for each type to minimize the population’s mass-weighted robust regret: \(\sum_t\mu_t\max_{\sigma\in R_t}\mathrm{MR}(H_\sigma(a_t),H_\sigma(A);W^1_{H_\sigma(\Lambda_t)})\). A solution is the type-to-recommendation policy and its objective value. It asks for the paper’s scale-sensitive recommendation calculation across a continuous population, while keeping the alternatives discrete.
My anchor is Theorem 3, proved in this paper. For finite \(A,\Lambda\), let \(E=\mathrm{Ext}(W^1_\Lambda)\); for each \(v\in E\), let \(s_v=\min_{\sigma\in R}v\cdot\sigma\), and let \(E'=\{v/s_v:v\in E\}\). The theorem states that the maximum, over rescalings in \(R\), of an alternative’s rescaled max regret equals its max regret over \(E'\), namely \(\max_{v\in E}D^A_v(\alpha)/s_v\), where \(D^A_v(\alpha)\) is the regret at \(v\). Thus each cohort’s robust-regret score can be evaluated by the paper’s finite extreme-point calculation. The population objective then separates by type: compute each alternative’s score for each type, choose a minimum-score alternative for that type, and weight the resulting scores by \(\mu_t\).
I expect this mirror to be tractable in the paper’s manageable-extreme-point regime. Its work depends on \(\tau\), the alternative sets, the extreme points and the rational input lengths—not on the raw number \(N\) of users. That is the high-multiplicity gain. The paper does not give a general polynomial-time guarantee when extreme-point sets may be exponential, so I would not claim unrestricted tractability. A natural next question is whether pricing or separation can avoid enumerating those points and yield a bound polynomial in the support and input length.
The authors could plausibly recognize this as an extension of their recommendation problem: a platform is making the same kind of recommendation under incomplete weighted-average preferences, but for many repeated cases. My weakest point is that Wilson studies a single user’s regret, whereas this mirror adds a population objective—the mass-weighted sum of cohort-level worst regrets. That aggregate is a modeling choice, not a result of the paper. It is most convincing for a service choosing recommendations by cohort and optimizing aggregate user loss; if the scale uncertainty must be one shared shock across all cohorts, the corresponding worst-case objective would instead maximize the sum over one common \(\sigma\), and Theorem 3 does not directly settle that variant.
The paper has no named NP-hardness or complexity-class theorem to anchor here. Theorem 3 is the relevant named computational result: it supplies the calculation that makes this particular population extension plausible. The mirror covers the scale-robust recommendation result, not every application or analysis in the paper.
Theorem 3 is a real computational anchor: it gives a formula for computing an alternative’s worst regret over a rescaling range, assuming the relevant extreme points are manageable. I would not argue that the paper has no computational result. The problem is that the proposed population version adds no population-level computation to that result.
Let \(g_t(a)\) be type \(t\)’s robust-regret score for recommendation \(a\). If users receive recommendations according to their type and the objective is the mass-weighted sum of their scores, then
\[ \min_{(a_t)}\sum_t\mu_t g_t(a_t) =\sum_t\mu_t\min_{a\in A}g_t(a). \]
Theorem 3 computes each \(g_t(a)\) from that type’s own extreme points. The masses only weight the final sum; they do not change the computation, create a transfer problem, or help with a large extreme-point set. With one repeated type, this is one call to the paper’s calculation. With many types, it is the same calculation repeated. So the proposed mirror is a batch application of Theorem 3, not a new high-multiplicity algorithmic question.
There is a regime concern as well. To be a complete type here, a user must share the relevant alternatives, preference constraints, and rescaling range. A platform could have many users in the same elicitation state, but rich, individualized preference histories may make the support large. Coarsening those histories into demographic or preference categories would no longer preserve the information the paper’s regret calculation uses. This makes the high-multiplicity regime possible, but narrower than the case for voting populations with recurring ballots.
The stronger repair is to couple users: for example, require one common recommendation for everyone, impose limited capacity across recommendations, or optimize aggregate regret under one shared rescaling. Those are plausible collective decision problems, but their coupling comes from a new policy or welfare choice. A common recommendation changes the paper’s individual recommendation task; capacity and fairness constraints add a separate allocation problem. A shared worst-case scale treats an analyst’s choice of units as an adversarial event for the whole population. Theorem 3 supplies per-user scores, but does not establish that any of these aggregate objectives is the right one.
That is the strongest negative case: the stated mirror is mostly repeated evaluation, and making it computationally richer requires adding a collective objective absent from the paper. But I would not claim the universal negative is secure. A high-volume service with a fixed menu and recurring preference profiles is credible, and a system choosing one public option for such a cohort could give the aggregate-regret extension a real application. Whether that is worth ChoCo’s time depends on accepting the added collective objective; the material here does not rule it out.
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.