| paper | d4-conf-aaai-2015-0485 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Polynomial-time solvable, including exact rational witnessing societies and all tied minimizers. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite set \(X\) of feasible plans with rational cost vectors, resident types \(T\) with positive normalized weight vectors \(w^t\), and a nonempty rational polytope \(\mathcal M\subseteq\Delta(T)\) of admissible population shares, compute the plans \(x\in X\) that minimize \(\sum_{t\in T}\mu_t w^t\cdot x\) for at least one \(\mu\in\mathcal M\), returning a witnessing distribution for each.
A city chooses one feasible plan for a population with type shares \(\mu\). Each type \(t\) has a complete preference vector \(w^t\); the city minimizes the plan’s average resident disutility, and survey information specifies the admissible share polytope \(\mathcal M\).
The mirror adds a collective welfare rule and uncertainty about population shares, while the paper elicits one decision maker’s private weights; the city-planning example makes this explicit but cannot establish that the authors would adopt that interpretation.
fatal: False
The mirror covers Theorem 1’s explicit finite-set computation of \(PO_\Omega(X)\); it leaves the implicit state-space search, elicitation strategies, and numerical results without a claimed population-complexity result.
A credible mirror is a city choosing among transit plans. Each plan is a path through a finite state space, with an additive cost vector such as travel time, fare burden, emissions, and unreliability. Residents share one of a modest number \(\tau\) of complete preference types, each a positive normalized weight vector over those criteria. A type’s mass is its fraction of the population. The regime is millions of residents represented by perhaps tens of types, rather than a small committee of individually modelled decision makers.
Suppose survey results leave the type shares uncertain within a rational polytope \(\mathcal M\). The authority evaluates a plan \(x\) by aggregate disutility \(\sum_{t\in T}\mu_t\,w^t\cdot x\), where \(w^t\) is type \(t\)’s weight vector and \(\mu\in\mathcal M\) is a possible society. For example, an observed population-level comparison between two plans can add a linear constraint on the shares. This preserves the paper’s additive path costs and linear preference model; the aggregate weight vector is \(\bar\omega(\mu)=\sum_t\mu_t w^t\).
My anchor is Theorem 1, proved in this paper. It states that Algorithm 1 returns exactly \(PO_\Omega(X)=\bigcup_{\omega\in\Omega}\arg\min_{x\in X}\omega\cdot x\): the cost vectors in a finite explicit set \(X\) that are optimal for at least one admissible weight vector in the convex polyhedron \(\Omega\). The paper’s analysis of the algorithm says it makes \(|X|\) linear-programming tests, so this explicit-set problem is polynomial-time. The theorem establishes the exact output; the polynomial-time claim comes from the accompanying algorithm analysis.
The continuous question I would hand to a prover is Population-Possible-Optimal Plan. An instance consists of a finite set \(X\) of rational cost vectors, each associated with a feasible path; a finite set \(T\) of rational positive normalized preference vectors \(w^t\); and a nonempty rational polytope \(\mathcal M\subseteq\Delta(T)\) of admissible population shares. Return
\[
P_{\mathcal M}(X)=\left\{x\in X:\exists\mu\in\mathcal M,\quad
x\in\arg\min_{y\in X}\sum_{t\in T}\mu_t\,w^t\cdot y\right\}.
\]
A solution is the exact set of such cost vectors, with one feasible path for each. A rational population witness \(\mu\) can accompany each output.
This is Theorem 1’s problem under the substitution \(\Omega=\{\bar\omega(\mu):\mu\in\mathcal M\}\), a linear image of the admissible population profiles. It asks which shared plans could be optimal under a society consistent with the available population information. The expected class is A for this explicit-set version: its LP filtering remains polynomial in \(|X|\), \(q\), \(\tau\), and the rational input description. The continuum is in the population shares; the plan space and criterion vectors remain as in the paper.
The scope is deliberately narrow: it mirrors Theorem 1’s explicit finite-set subproblem. It does not claim a complexity result for the paper’s implicit state-space search or its query-selection strategies. Those suggest follow-up questions: can the possible-optimal plans be generated efficiently when paths are implicit, and which population-level queries most reduce worst-case regret? There is no numbered hardness result in the paper to use as an anchor.
The soft spot is the social interpretation. The paper studies one decision maker with uncertain weights; this mirror treats that decision maker as a public authority aggregating many residents’ priorities by linear welfare. That is a real modelling choice, and an author who intends only to recover one person’s private preferences could reject it. In the city-planning setting, though, it gives each resident a complete type, makes mass the natural unit for uncertain representation, and leaves the paper’s central question intact: which feasible path minimizes a linear scalarization for some admissible weight vector?
Theorem 1 is a real computational anchor: it proves that Algorithm 1 returns exactly \(PO_\Omega(X)\), and the paper explains that this takes \(|X|\) bounded-size linear programs. So I would not argue that the paper lacks a computational result.
The proposed \(P_{\mathcal M}(X)\), though, changes what is uncertain. In the paper, one decision maker has an unknown personal weight vector; \(\Omega\) records which vectors remain consistent with her preferences. In the mirror, residents have different weight vectors, their utilities are summed, and \(\mathcal M\) records possible population compositions. That is a coherent group-planning model, but its aggregate-welfare assumption and uncertainty about the electorate are additions, not a high-multiplicity version of the paper’s elicitation problem.
The distinction matters for the anchor. With a known society \(\mu\), the objective reduces to a single aggregate vector \(\bar\omega(\mu)\). The theorem’s question about which plans are optimal for *some* admissible weight vector then disappears. Retaining that question requires a set \(\mathcal M\) of possible societies, so the instance is uncertainty about the population rather than the specified distribution over types. And the paper’s preference queries ask one person to compare plans; a population-level comparison needs a rule for combining residents’ answers. Calling it a population-level comparison does not supply that rule.
A stronger mirror could make the group interpretation explicit: a city chooses one transit plan to minimize residents’ average disutility, while surveys constrain the type shares. That may be worthwhile research, and it preserves the algebra of the theorem. But its value rests on the new collective objective and survey model being a question these authors would recognize as theirs. If that interpretation is accepted, the negative case fails; the material here cannot rule it out. My case against is therefore strongest as a challenge to treating this anchor as an established continuous-population mirror, not as proof that no useful group-planning mirror exists.
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.