| paper | d4-conf-aaai-2023-1203 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: NP-hard to approximate within \(c(\ln(1/\epsilon)+\log\tau)\) for a universal constant \(c>0\), even with polynomial-size circuits and dyadic rational data. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite set of tests \(U\), a finite type support \(T\) with positive binary-rational masses \(\mu_t\) summing to \(1\), and for each type \(t\) explicitly represented monotone submodular functions \(f_{tj}:2^U\to[0,1]\) with \(f_{tj}(U)=1\) and positive weights \(a_{tj}\), find a permutation \(\pi\) minimizing \(\max_{t\in T}\mu_t\sum_j a_{tj}\operatorname{cov}(f_{tj},\pi)\), where \(\operatorname{cov}(f_{tj},\pi)\) is the first prefix length at which \(f_{tj}\) reaches \(1\).
A type is a cohort's complete diagnostic profile: its hypothesis functions and weights. The society is the distribution \(\mu\) over those profiles; all cohorts use one discrete test ordering, and each cohort's weighted cover time is multiplied by its population share.
The formal SRMA and diagnostic framing maximize per-agent expected cover time, while the proposed \(\mu_t\) factor maximizes cohort total workload; the web-search discussion supports group totals but does not establish that the authors would use this criterion for diagnosis.
fatal: False
The mirror captures Theorem 3's min-max SRMA inapproximability over cohort types, including the multiple-distribution decision-tree setting. It leaves the approximation algorithms, GMSC result, and experiments outside its scope.
The strongest mirror I see is a population version of the paper’s non-adaptive, min-max decision-tree problem. Take a large population of patients divided into demographic cohorts. A type is a cohort’s complete diagnostic profile: the possible hypotheses, their probabilities, and the tests and outcomes that distinguish them. People in a type share that profile; \(\mu_t\) is the fraction of the population in that cohort. The number of people \(N\) can be much larger than the number of types \(\tau\).
Here is the underlying problem. The input has a finite set \(U\) of tests, a finite support \(T\) of \(\tau\) types with rational masses \(\mu_t>0\) summing to \(1\), and, for each type \(t\), monotone submodular functions \(f_{tj}:2^U\to[0,1]\) with \(f_{tj}(U)=1\), and positive weights \(a_{tj}\). Each function is given by a succinct representation supporting exact evaluation; the hardness instances can be represented explicitly as coverage functions. For an ordering \(\pi\) of the tests, let
\[
\operatorname{cov}(f_{tj},\pi)
=\min\{r:f_{tj}(\{\pi_1,\ldots,\pi_r\})=1\}.
\]
The question is to find a permutation \(\pi\) minimizing
\[
\max_{t\in T}\ \mu_t\sum_j a_{tj}\operatorname{cov}(f_{tj},\pi).
\]
In the diagnostic interpretation, \(a_{tj}\) can be the probability of hypothesis \(j\) for type \(t\). The quantity inside the maximum is that cohort’s share of the population multiplied by its expected number of tests: its normalized contribution to total diagnostic workload. This is a common, non-adaptive test order, and a solution is a full permutation. The society is the continuous object; the tests, order, and cover times remain discrete.
My anchor is Theorem 3, proved in this paper by combining its multiple-agent lower bound with the single-agent submodular-ranking lower bound of Azar and Gamzu (2011). It says that, unless \(P=NP\), min-max submodular ranking for multiple agents cannot be approximated within \(c(\ln(1/\epsilon)+\log k)\) for some constant \(c>0\), where \(k\) is the number of agents and \(\epsilon\) is the smallest nonzero marginal value among their functions. The paper’s own Lemma 5 supplies the multiple-agent \(\log k\) hardness; the cited earlier result supplies the single-agent \(\ln(1/\epsilon)\) hardness.
That hardness transfers directly to the stated population problem. Given any \(k\)-agent instance, make \(k\) types of equal mass \(1/k\), with each type carrying that agent’s functions and weights. The population objective is then exactly \(1/k\) times the paper’s objective, so the optimizer and approximation ratio are unchanged, as is \(\epsilon\). Thus the continuous problem inherits the inapproximability with \(\tau\) in place of \(k\). I expect hardness to transfer (Class B): the reduction’s combinatorics can live in the number of distinct profiles, not just in a large headcount. This does not show that large populations with small \(\tau\) are hard for the same reason; whether low support enables stronger guarantees is one of the natural follow-up questions.
The cohort interpretation is credible for these authors because the paper already treats agents as groups, and its web-search discussion explicitly describes a group’s total satisfied time. Multiplying a cohort’s per-capita expected cover time by its population share makes that aggregate burden explicit, while staying inside the paper’s weighted min-max objective. The mirror covers the multiple-agent submodular-ranking and non-adaptive decision-tree results; it does not continuize the outcome space or replace their computational question with an analytic one.
The weakest point is the choice of fairness metric. The paper’s objective takes a maximum of agent costs without multiplying by population share. My mirror asks for the maximum mass-weighted cohort burden, which can favor protecting large cohorts over equally protecting each cohort per capita. That choice fits the paper’s total-group-workload interpretation and is expressible through its weights, but an author who intends strict per-capita fairness may reject it. For that interpretation, mass would identify which types are present but would not affect the maximum—making the continuous-population aspect less substantive.
The strongest objection is that the paper’s “agents” are already whole decision environments: each carries a prior over hypotheses, a family of submodular functions, and weights. Under the paper’s per-agent fairness objective, turning agents into demographic types and assigning them population masses gives
\[
\max_{t:\mu_t>0}\sum_j a_{tj}\operatorname{cov}(f_{tj},\pi).
\]
Changing a cohort’s size has no effect as long as it remains present. The society’s proportions are absent from the objective; only its support matters. That makes this a thin population mirror: it preserves the paper’s robust comparison across environments, while the proposed continuous masses do no computational work.
Weighting each term by \(\mu_t\) gives masses a role, but it changes the fairness criterion. It measures the largest cohort’s total workload, so a small cohort can receive little protection; with increasingly many types, the largest mass can shrink toward zero. This is a substantive concern, though the paper’s web-search discussion explicitly describes total satisfaction time for a user group, so the authors may well accept this interpretation. It cannot be ruled out as a mirror.
That concession leaves Theorem 3 standing. Equal masses reproduce its objective up to a common factor, and the paper itself motivates agents as groups. I do not see an honest way to defeat that anchor under the programme’s gate. The negative case is weak: its best point is that the per-capita version makes population mass irrelevant, while the more population-sensitive version alters the fairness objective. Since the paper offers a group-total interpretation, a worthwhile continuous mirror remains plausible.
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.