| paper | d4-conf-ijcai-2015-0442 |
| 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: \(\mathrm{NP}\text{-hard}\); a polynomial bound on total computation and oracle calls would imply \(\mathrm P=\mathrm{NP}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite directed path graph, nonnegative additive criteria, a finite support \(T\) of complete resident preference types, and a rational polytope \(\mathcal M\subseteq\Delta(T)\) of possible population shares, let \(F_\mu(p)=\sum_{t\in T}\mu_t\psi_t(g(p))\). With pairwise comparison answers determined by an unknown \(\mu^*\in\mathcal M\), can an interleaved search and elicitation procedure return a path \(p\) whose regret \(\max_{\mu\in\mathcal M}\bigl(F_\mu(p)-\min_{p'}F_\mu(p')\bigr)\) is at most a given tolerance \(\delta\), after refining \(\mathcal M\) from those answers?
A public planner chooses one route for a large population with finitely many complete preference types and uncertain rational type shares; resident welfare is the share-weighted average disutility.
The remaining concern is that the mirror assumes a planner whose objective is average resident disutility and whose comparison answers constrain the share polytope; the paper does not specify that collective decision process.
fatal: False
The mirror covers Theorem 1’s robust approximate path recommendation for uncertain population shares; it leaves the paper’s other search details, experiments, and preliminary elicitation of one-dimensional disutility functions outside the proposed result.
The strongest honest anchor is Theorem 1, proved in this paper. The paper gives no named NP-hardness or polynomial-time classification; this theorem is its clearest named computational guarantee. In the paper’s notation, \(g_S\) is the set of cost vectors for paths currently in the candidate set, \(ND(X)\) is the Pareto frontier of feasible path costs, and \(MMR_\epsilon\) is the minimum, over candidates in \(g_S\), of their worst-case \(\epsilon\)-regret over the remaining weight uncertainty set \(\Omega\). Theorem 1 states that if, at the end of the search, \(MMR_\epsilon(g_S,\Omega)\le(1+\epsilon)\delta\), then the selected path \(p^*\) has ordinary maximum regret at most \(\delta\) against \(ND(X)\).
There is a caveat in the result as printed: its statement selects \(p^*\in\arg\min MR(g_\ell,g_S,\Omega)\), but the proof starts by selecting \(p^*\in\arg\min MR_\epsilon(g_\ell,g_S,\Omega)\). The proof’s guarantee follows for the latter selection. I would treat that as a correction the authors should make before relying on the theorem as written; the population analogue below uses the proof’s selection rule.
A plausible mirror is Population-Type Robust-Regret Path Search. Its instance is a finite directed graph with source, goal nodes, and \(q\) nonnegative additive path criteria, such as time, distance, energy, and risk. The affected population has a known support \(T\) of \(\tau\) complete preference types. A type specifies the person’s full disutility model, such as an additive utility or Choquet integral. The true population has shares \(\mu\in\Delta(T)\), but only partial information about those shares is available, represented by a rational polytope \(\mathcal M\subseteq\Delta(T)\). Each feasible share vector is a possible society; pairwise judgments by the population’s decision process restrict \(\mathcal M\).
For path \(p\), define its aggregate disutility in society \(\mu\) by
\[
F_\mu(p)=\sum_{t\in T}\mu_t\psi_t(g(p)).
\]
The question is: given the graph, type models, current \(\mathcal M\), and a tolerance \(\delta\), search for one path \(p\) and, if needed, adaptively elicit aggregate comparisons between paths until the remaining uncertainty supports a \(\delta\)-regret recommendation. A solution is a path with
\[
\max_{\mu\in\mathcal M}\left(F_\mu(p)-\min_{p'\in P(s,\Gamma)}F_\mu(p')\right)\le\delta.
\]
The paper’s \(\epsilon\)-regret stopping condition transfers by replacing \(\Omega\) with \(\mathcal M\) and the individual scalarization value with \(F_\mu\).
The population regime is a large public planning process: many residents are affected by a route or infrastructure plan, while their criterion-weight profiles fall into a relatively small number of recurring types. For example, a city may have millions of affected residents but comparatively few distinct profiles of time sensitivity, accessibility needs, and risk tolerance. Each \(\mu_t\) is a share of residents, rather than a count of individually addressable people. The polytope represents uncertainty about those shares after aggregate consultation.
This is a credible extension of the paper’s problem. It keeps the same implicit path space, criteria, robust-regret objective, search, and pairwise elicitation. Also, \(F_\mu(p)\) is linear in the population masses, so the paper’s LP-based dominance tests have a direct counterpart. The authors would likely recognize it as their robust search problem with a group-level preference model, though the collective aggregation rule is an added modeling choice.
For this anchor, I expect the mass-uncertainty layer to be tractable: its optimization remains linear in \(\mu\). I would tentatively place the stated approximate recommendation problem in Class A when the graph search is manageable, but Theorem 1 does not prove polynomial running time for arbitrary graphs. The path-search combinatorics remain, so any hardness of the underlying graph problem would likely transfer; the paper establishes no such hardness result, and I would not claim one here. This mirror covers the paper’s robust approximate recommendation procedure, not its full treatment of all preference models or the preliminary elicitation of one-dimensional disutility functions.
The weakest point is the move from one decision maker’s uncertain weight vector to a population distribution and a collective objective. The mass variables make the problem continuous, but the authors must accept average type disutility as the group’s decision rule. That is a substantive extension. The linearity and shared path-search structure make it a defensible one, but author recognition is less certain than for a mirror that changes only the representation of the original decision maker’s uncertainty.
The best case against is that Theorem 1’s uncertainty is about one decision maker’s coherent preference model, not about a society. Its guarantee concerns a path chosen under uncertainty over that person’s parameters \(\Omega\). The paper does not give a polynomial-time classification, and Theorem 1 itself is conditional: it certifies a regret bound if the search ends with the stated \(MMR_\epsilon\) bound. There is also a mismatch between the theorem’s stated choice of \(p^*\) and the choice used in its proof; correcting that mismatch would fix the statement, but would not turn it into a complexity result.
The proposed city-planning mirror can be made mathematically clean. Give each resident a complete preference type \(t\), and choose a route by minimizing average disutility, \(F_\mu(p)=\sum_t\mu_t\psi_t(g(p))\). But with known shares, this averages the residents into one composite decision maker. With uncertain shares, comparisons constrain the mass vector just as preference comparisons constrain the original parameter vector. In either case, the population version largely re-expresses the paper’s existing preference-uncertainty model; it does not expose a distinct search problem created by high multiplicity. That makes it hard to justify as a new continuization result rather than an application of the existing one.
To give population mass a distinct role, one could instead use majority choice, fairness, or personalized recommendations. Then the key question is how the group’s preferences are aggregated, or how paths are allocated among people. Those are consequential modeling choices, but they supply a new collective-choice or allocation problem that the paper does not study. The theorem’s regret guarantee would not settle them merely by replacing \(\Omega\) with a polytope of population shares.
This is a fit-and-novelty objection, not a proof that no worthwhile mirror exists. A collective planner using average resident disutility is plausible, and the theorem may transfer to that model. I cannot honestly rule out every such scenario; the negative case is weakest precisely at the point where an author could accept that planner as the decision maker and treat the population’s type shares as the uncertainty.
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.