| paper | d4-conf-ecai-2014-0192 |
| 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: Polynomial-time solvable: in \(\mathrm P\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
Let \(\mathcal C_n\) be the polytope of Choquet capacities and \(T=\operatorname{ext}(\mathcal C_n)\) its extreme capacities, treated as voter types. Given rational alternatives \(X\subseteq[0,1]^n\) and aggregate elicitation statements \(P\) that constrain \(\bar v_\mu(A)=\sum_{t\in T}\mu_t v^t(A)\), where \(\mu\) is an unknown society distribution over \(T\), choose \(x\in X\) minimizing \(\max_{\mu\text{ consistent with }P}\max_{y\in X}\bigl(C_{\bar v_\mu}(y)-C_{\bar v_\mu}(x)\bigr)\).
A continuous population of customers with Choquet-capacity types; the decision is a recommended alternative, and the objective is its worst-case aggregate Choquet regret over societies consistent with the elicitation history.
The masses affect regret only through the mean capacity \(\bar v_\mu\), and the proponent does not fully establish that the authors would treat an unobserved composition as a population input rather than a relabeling of capacity uncertainty.
fatal: False
The mirror covers the capacity-completion result and pairwise max-regret recommendation for a utilitarian panel; it leaves the paper's query-selection heuristic and distribution-sensitive or majority-based group decisions outside its scope.
The best positive case is a collective version of the paper’s minimax-regret recommendation problem. The paper has no numbered theorem asserting a complexity classification. My sole named anchor is Proposition 1, proved in this paper: for \(\mathcal A\subseteq 2^N\), any partial function \(v:\mathcal A\to[0,1]\) whose values satisfy \(v(A)\in[l_A,u_A]\) and \(v(A)\le v(B)\) whenever \(A\subset B\) in \(\mathcal A\) can be completed to a capacity in \(\Theta_P\). The authors use this completion result to remove irrelevant monotonicity constraints when computing pairwise maximum regret. It is a computationally useful structural anchor, though it does not itself state that a problem is in P.
A plausible population is a large customer base choosing among products or services. A type is a customer’s complete Choquet capacity over the criteria—for example, how that customer trades off price, reliability, and environmental impact, including interactions between criteria. Customers of the same type share that capacity; \(\mu_t\) is their fraction of the population. Take the type universe to be the extreme capacities of the capacity polytope. For any society, its mean capacity
\[
\bar v_\mu(A)=\sum_t\mu_t v^t(A)
\]
is itself a capacity, and linearity of the Choquet integral gives
\[
\sum_t\mu_t C_{v^t}(x)=C_{\bar v_\mu}(x).
\]
Conversely, any capacity is a mixture of extreme capacities. Thus this population model gives a precise interpretation of the paper’s uncertain capacity: it is the mean preference of a heterogeneous panel. By Carathéodory’s theorem, a mean capacity can be represented using at most \(2^n-1\) types, so a population of millions can still have a modest type support when the number of criteria is modest.
Here is the problem I would give a prover, which I’ll call Continuous Choquet Panel Minimax-Regret Recommendation. The instance consists of a finite set \(X\) of alternatives with rational performance vectors in \([0,1]^n\), and the panel’s elicitation history \(P\). Each statement in \(P\) is an aggregate comparison of the paper’s form \(1_A0\succeq\Lambda\) or \(1_A0\preceq\Lambda\); it bounds \(\bar v_\mu(A)\). The actual population has rational type masses, but its composition is not yet known to the recommender. The task is to return
\[
x^\star\in\arg\min_{x\in X}\ \max_{\mu\text{ consistent with }P}\ \max_{y\in X}
\left(C_{\bar v_\mu}(y)-C_{\bar v_\mu}(x)\right).
\]
A solution is the recommended alternative \(x^\star\), with its worst-case regret. This is an aggregate-welfare query, not a majority-vote query: a panel comparison reflects average Choquet utility. The mean-capacity identity makes that assumption explicit and lets Proposition 1 apply to the bounds learned from those comparisons.
I expect this full-capacity version to be tractable. The paper’s reduced pairwise-regret LP uses only the level sets of the two alternatives, with \(O(n)\) variables and constraints; considering all pairs in \(X\) then gives a polynomial-time minimax recommendation algorithm. That complexity conclusion comes from the paper’s LP and unnumbered iterative algorithm, not from Proposition 1 alone. A natural next question is whether selecting the next panel query by the paper’s worst-case minimax-regret criterion remains tractable when the population’s type support or feasible mass distributions are explicitly restricted. Those restrictions can shrink the set of possible mean capacities, so Proposition 1 may no longer suffice.
The weakness is that the paper studies one decision maker, while this mirror treats a group as having utilitarian aggregate preferences. Its authors could reasonably accept it as a collective extension because the group’s utility is exactly another Choquet integral, but they might reject it as a change of problem. Also, if the panel’s exact masses were already known, there would be no capacity uncertainty to elicit. The mirror therefore covers the paper’s pairwise-regret computation and robust recommendation, with the population composition hidden during elicitation; it does not claim to mirror the paper’s query-selection heuristic or all its results.
The strongest objection is that the proposed panel has no population-specific computational problem. For each alternative \(x\), linearity in the capacity gives
\[
\sum_t \mu_t C_{v^t}(x)=C_{\bar v_\mu}(x),
\qquad
\bar v_\mu(A)=\sum_t\mu_t v^t(A).
\]
The mean \(\bar v_\mu\) is a capacity, and every capacity can be represented as a mixture of extreme capacities. So the panel’s possible mean capacities are exactly the paper’s possible capacities \(\Theta_P\). The proposed minimax regret and aggregate queries therefore reduce term for term to the paper’s own regret computation and elicitation procedure. The type masses disappear from the calculation.
That matters because the programme’s society is an input: its types and rational masses are given. If the panel’s capacities and masses are known, its aggregate capacity is known and there is no elicitation uncertainty. If only aggregate comparisons are known, the task is the paper’s uncertainty over one capacity, with an unobserved population supplying an interpretation rather than computational input. Proposition 1 does not analyze masses or support; it completes partial values of that aggregate capacity. It is a useful structural result, but not a complexity result about populations.
A distribution-sensitive version could make the population matter—for example, querying individual types or seeking a majority choice rather than maximizing aggregate utility. But then the objective and the information being elicited change, and Proposition 1 no longer anchors the problem. That could be a worthwhile group-decision project, but it is a different extension, with its own assumptions about polling, types, and group choice.
I can’t honestly rule out every such extension. The negative case is strongest against this anchor: its faithful utilitarian version collapses to the paper’s existing model, while versions that preserve information about the distribution move away from the result being mirrored.
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.