| paper | d4-conf-atal-2021-0298 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: The decision problem is \(\mathrm{NP}\)-complete, and exact optimization is \(\mathrm{NP}\)-hard, even with binary catalogue coordinates, equal masses, and uncertainty polytopes of dimension \(p-1\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Lemma 3.2
statement extracted from the paper’s text layer
Given a rational catalogue \(A\subseteq\mathbb{Q}^p\), a shortlist size \(k\), and \(\tau\) preference types with rational masses \(\mu_t\geq 0\), \(\sum_t\mu_t=1\), and nonempty rational uncertainty polytopes \(W_t\subseteq\{w\in\mathbb{R}^p:w_i\geq0,\sum_i w_i=1\}\), find a common \(k\)-item shortlist \(B\subseteq A\) minimizing \(R_\mu(B)=\max_{(w_t)\in\prod_t W_t}\sum_t\mu_t\bigl(\max_{a\in A}a\cdot w_t-\max_{b\in B}b\cdot w_t\bigr)\), and compute its exact value.
Types are preference and uncertainty descriptions \(t\), each with mass \(\mu_t\) and feasible weight polytope \(W_t\). The catalogue items remain indivisible; binary decisions \(y_a\in\{0,1\}\) select the common shortlist with \(\sum_{a\in A}y_a=k\). Minimize worst-case per-capita aggregate regret over the product of type uncertainty sets.
The mirror extends database setwise minimax regret and its SAT-pruning idea to a shared shortlist for multiple types. It does not cover the paper’s configuration-problem discussion or establish the multi-type algorithm’s performance; the reported experiments remain results for the single-decision-maker model.
The strongest honest case is a population version of the paper’s database setwise minimax regret problem. There is a qualification: the paper has no numbered theorem or lemma classifying SMMR as polynomial-time solvable or hard. The best defensible anchor is Lemma 3.2, proved here. It is a computational lemma used in the SAT-pruning algorithm, rather than a complexity classification.
Lemma 3.2 says: if \(r\) is an upper bound on \(\mathrm{SMMR}^{k}_{W}(A)\), \(W'\subseteq W\), and \(B\subseteq A\), define \(\Gamma_w=\{\alpha\in A:\mathrm{Val}_A(w)-u_w(\alpha)<r\}\). Then \(\mathrm{SMR}_{W'}(B,A)<r\) exactly when, for every \(w\in W'\), \(B\) contains some alternative in \(\Gamma_w\). The paper uses this characterization to build a cardinality-constrained SAT test: if no size-\(k\) extension of a partial set can meet the conditions for every \(w\in W'\), the search can prune that branch. This is the paper’s relevant named result; Algorithm 1 itself is not a numbered theorem.
My proposed mirror is Type-Weighted Setwise Minimax Regret. The scenario is a large service or retailer that shows one common shortlist from an explicit catalogue to a large cohort. The cohort may have millions of users but only \(\tau\) preference types, such as recurring user segments with the same criteria trade-offs and elicitation history. A type is a complete preference description for this problem; its mass \(\mu_t\) is its share of the cohort. The catalogue is \(A\subseteq\mathbb{Q}^p\), with each item’s \(p\) criterion scores. For each type \(t\), \(W_t\) is a nonempty rational polytope of still-possible weight vectors in the unit simplex.
Given a shortlist size \(k\), choose one common \(B\subseteq A\), \(|B|=k\), minimizing
\[ R_\mu(B)= \max_{(w_t)\in\prod_{t\in T}W_t} \sum_{t\in T}\mu_t \left( \max_{a\in A} a\cdot w_t - \max_{b\in B} b\cdot w_t \right). \]
The solution is the shortlist \(B\) and its exact worst-case per-capita regret. Users still receive and choose among whole catalogue items; mass weights the cohort’s aggregate loss. The corresponding finite-population version has \(n_t\) copies of each type, with \(\mu_t=n_t/\sum_t n_t\). Thus a small support \(\tau\) can describe a much larger population.
The connection to Lemma 3.2 is strongest for \(\tau=1\), where this is exactly the paper’s SMMR problem. For multiple types, the same common-shortlist and regret primitives remain, but the pruning condition becomes a weighted sum across types; adapting the SAT test would require additional encoding work. The authors could plausibly recognize this as a group recommendation extension of their problem, especially since their setwise regret already evaluates a set offered to a user who picks their favorite item. They would also be right that the population aggregation is new: the lemma does not establish an algorithm or complexity result for it.
My prior is Class B: hardness should transfer if the finite grouped-user shortlist problem is shown hard, since rational type proportions represent finite multiplicities and the shortlist still requires selecting \(k\) indivisible items. That is a research expectation, not a result of this paper. The main questions are whether hardness already holds for small \(\tau\), whether fixed \(k\) or bounded \(p\) helps, and whether the multi-type regret objective admits an exact SAT or optimization formulation that extends the paper’s pruning method.
The weakest point is the cohort scenario: a shared shortlist for a large population is plausible, but this paper studies one decision-maker, and it does not analyze aggregate regret across preference types. So the mirror covers the paper’s exact database SMMR problem and its named SAT-pruning lemma, not its configuration-problem discussion or its experimental speedups as separate results.
The anchor is Lemma 3.2, but it is not a complexity result. It proves a pruning condition for a finite catalogue and one decision-maker’s uncertainty set: a set has regret below \(r\) on \(W'\) exactly when it covers the alternatives in \(\Gamma_w\) for each \(w\in W'\). That justifies a step in the algorithm; it says nothing about the complexity of SMMR. The paper’s named result therefore gives ChoCo little complexity landscape to continue.
The strongest repair is a shared-shortlist problem for a large cohort. Give each complete user type \(t\) a mass \(\mu_t\) and uncertainty polytope \(W_t\), then choose one \(k\)-item shortlist \(B\) to minimize
\[ \sum_t \mu_t \max_{w\in W_t} \bigl(\mathrm{Val}_A(w)-\mathrm{Val}_B(w)\bigr). \]
That is a coherent high-multiplicity model. But with one type, the mass cancels and the problem is exactly the paper’s SMMR problem. With multiple types, the nontrivial question is how to choose a *common* shortlist for a group: the objective has changed from one user’s regret to aggregate group regret. If users instead get individual shortlists, the problem separates by type. The paper’s lemma does not settle the coupled group version: its threshold-cover condition does not encode a weighted sum of type-level regrets.
That is the strongest case against treating this paper as a worthwhile continuization target: its only named computational anchor is a correctness lemma for a single-user pruning rule, and the richer population version needs a new group objective and new algorithmic results. Still, the universal claim is weak. A service that really must show one catalogue shortlist to a large, heterogeneous cohort is a plausible scenario, and the group problem could be worth studying. I cannot honestly rule out a mirror the authors would recognize; I can only argue that it is an adjacent extension, not a direct continuization of the paper’s anchored result.
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.