| paper | d4-conf-ecai-2024-0007 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 23
statement extracted from the paper’s text layer
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)\).
A large population receives one recommendation from a common finite slate \(A\). Each type \(t\) consists of users with the same comparison record \(\Lambda_t\), hence the same compatible preference cone \(V_{\Lambda_t}\); \(\mu_t\) is its population mass. Choose \(a\in A\) to minimize the mass-weighted sum of each type’s worst-case \(D_1\)-relative regret.
The paper studies compromise across one user’s uncertain preference models; averaging worst-case regret across distinct cohorts adds a collective welfare rule that the paper does not select.
fatal: False
Covers \(D_1\)-relative-regret computation and choosing a shared recommendation from those values; leaves the paper’s invariance results, other \(D_k\) variants, and query-generation uses outside the population mirror.
The strongest mirror I see is a Population \(D_1\)-Regret Recommendation problem. Imagine a large service choosing one default recommendation from a shared finite slate \(A\) for a population of users. Everyone is evaluated on the same \(p\) objectives, but users have answered different sets of preference questions. Type \(t\) is a group with the same slate and objective values and the same comparison record \(\Lambda_t\), so its compatible weight vectors are \(V_{\Lambda_t}=\{w\in\mathbb R^p_{\ge0}:w\cdot\lambda\ge0\text{ for every }\lambda\in\Lambda_t\}\). The population is a distribution \(\mu\) over the \(\tau\) supported types. Here \(w\) represents an uncertain preference model within a type, not a person in the population.
The precise question is: given rational alternative vectors \(A\), rational comparison records \(\Lambda_t\), and rational masses \(\mu_t\) summing to \(1\), choose one \(a\in A\) minimizing the population’s average typewise worst-case normalized regret, \(\sum_t\mu_t\,\mathrm{MRR}^{D_1}_A(a;V_{\Lambda_t})\). Return an exact minimizing alternative and the exact minimum value, including ties. For this paper’s \(D_1\), the denominator is the range of utilities across the alternatives: \(D^1_A(w)=\operatorname{Val}_A(w)-\operatorname{Wor}_A(w)\). Thus each cohort is scored by its worst regret relative to its own utility range, and the common recommendation minimizes the mass-weighted average of those scores.
My anchor is Theorem 23, proved in this paper. I rely on its \(D_1\) entry: for finite \(\Lambda\), finite \(A\), and \(\alpha\in A\), \(\mathrm{MRR}^{D_1}_A(\alpha;V_\Lambda)\) is finite and equals \(\max_{\beta,\gamma\in A}\max\{w\cdot(\beta-\alpha): w\in V_\Lambda,\ w\cdot\beta\ge w\cdot x\ge w\cdot\gamma\ \forall x\in A,\ w\cdot(\beta-\gamma)=1\}\), with the maximum of an empty set taken to be zero. The paper computes this using linear maximization. It contains no comparable hardness result, so this is an algorithmic anchor rather than a claim that discrete hardness dissolves.
The regime is plausible for a platform or organization serving a very large cohort from a common slate after a short, fixed comparison questionnaire. Users with the same answers have the same \(\Lambda_t\) and the same robust-regret calculation; with a fixed number \(r\) of yes/no comparisons, there are at most \(2^r\) response types even as the population grows. The mass is the fraction of users in each response group. This makes the population itself continuous while retaining the paper’s alternatives, linear preference models, uncertainty sets, and regret measure. The group-level default is an added collective decision, but the paper’s motivation includes recommending compromise alternatives, so this is a recognizable extension of that use.
I expect this problem to be Class A. For each type and candidate, Theorem 23 gives a polynomial number of LPs over the preference cone; then the algorithm forms the rational mass-weighted sums and picks the best of the finite alternatives. With explicit rational input, the resulting running time is polynomial in \(p\), \(\tau\), \(|A|\), the comparison-record sizes, and their bit lengths. Further questions include whether average typewise robust regret is the right population objective, whether a worst-cohort or fairness constraint preserves tractability, and what changes if the alternative set is implicit rather than explicit.
This mirror covers the paper’s computation of \(D_1\)-relative regret and its use in choosing a compromise alternative. It does not mirror the paper’s scale- and translation-invariance results or its query-generation methods. The weak point is the population objective: averaging each cohort’s worst-case regret is a defensible group-recommendation rule, but it is an extra modeling choice that the paper does not make. The computation also reduces to applying the paper’s LP method across types; it does not expose a new hardness boundary or a deep interaction between population mass and the recommendation.
Theorem 23 is a genuine computational anchor: it gives an exact LP formulation for computing \(D_1\)-relative regret. So the case against cannot say the paper has no computational result to mirror.
The stronger objection is that the theorem’s population analogue changes the decision problem. In the paper, \(W\) describes one user’s uncertain preferences, and the regret calculation supports a recommendation to that user. A list of cohorts with different query histories is not, by itself, a population version of that problem. If each cohort gets its own recommendation, the calculations are independent and the masses do not matter. If everyone must receive one recommendation, the objective \(\sum_t \mu_t\,\mathrm{MRR}^{D_1}_A(a;V_{\Lambda_t})\) adds a group welfare rule the paper does not study. Its “compromise” is a compromise across one user’s possible models, not across different users.
The proponent’s improved scenario—a platform choosing one default from a shared slate for a large population—is plausible. It avoids treating query answers as actual preferences: each cohort can be evaluated by its robust loss, and the population masses determine how those losses count. The resulting problem is well-defined, and Theorem 23 makes it polynomial-time solvable by computing each cohort’s regret and then taking the weighted sums. That is the best version of the anchor, and it is hard to dismiss as incoherent.
What keeps the negative case alive is the programme’s recognition gate. The paper gives no reason to think its authors would regard choosing a group default by average cohort regret as their problem, rather than as a new application built on their computation. The mirror’s central step is precisely the added collective objective; the continuous population supplies weights for that objective but does not alter the regret optimization itself. Still, this is a boundary argument, not a decisive one: the group recommendation is credible enough that the anchor may survive if the authors accept that extension. The honest negative case against this paper is therefore 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.