| paper | d4-conf-aaai-2002-0093 |
| 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: NP-hard under polynomial-time Turing reductions. An exponential output-size lower bound also rules out polynomial time in the stated input parameters. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given τ customer types with rational masses μ_t, type-specific finite-domain CSPs with feasible configurations ℱ_t, and shared comparable criteria and preference orders, choose masses y_{tq} ≥ 0 with ∑_{q∈ℱ_t} y_{tq} = μ_t. Each individual receives an integral configuration q, while cohort criterion j is z_j(y) = ∑_t ∑_{q∈ℱ_t} y_{tq} f_{tj}(q). Determine the exact set of attainable aggregate criterion vectors that are G-preferred under the paper’s Definition 4, with a finite symbolic description and a feasible allocation witness for each represented outcome.
A distribution over customer types, each with a finite-domain configuration problem and rational mass; mass variables allocate each type across integral configurations. Shared, comparable cohort criteria are linear in those masses, and the task is to represent the G-preferred aggregate frontier with allocation witnesses.
The paper optimizes one CSP solution, while the mirror adds a planner’s cross-customer aggregation of criteria; the service scenario makes this coherent, but the paper does not motivate that aggregation itself.
fatal: False
The mirror covers the G-preferred cohort configuration frontier associated with Theorem 3. It leaves the B-preferred extreme solutions of Theorem 2, balanced solutions, and preference projection outside its scope.
The strongest mirror I can defend is multi-criteria configuration for a large cohort. There is an important limit to the evidence: the paper states no numbered result that classifies a problem as polynomial-time, NP-hard, FPT, or similar. Its named computational theorems prove what its algorithms compute, not their running time. So this can support a continuous-complexity question, but it cannot be presented as a complexity result already established by the paper.
For a cohort version, let a type \(t\) be a complete finite-domain CSP specification: its requirements, constraints, catalog data, criteria, and preferences are all the same for every person of that type. A society is a distribution \(\mu\) over the \(\tau\) supported types, with rational masses summing to one. A plausible regime is a large travel or product service serving many recurring customer profiles: \(N\) is very large while \(\tau\) is relatively small. This is not the paper’s single-user vacation-adviser problem; it is a cohort portfolio problem built from the same configuration problems.
For type \(t\), let \(\mathcal F_t\) be its set of feasible configurations, and let \(f_{tj}(q)\) give configuration \(q\)’s value on criterion \(j\). The decision is a mass allocation \(y_{tq}\geq 0\), with \(\sum_{q\in\mathcal F_t}y_{tq}=\mu_t\). Thus each customer still receives an integral configuration, while \(y_{tq}\) is the fraction of type \(t\) assigned configuration \(q\). The cohort criterion is \(z_j(y)=\sum_t\sum_{q\in\mathcal F_t}y_{tq}f_{tj}(q)\). A solution is such an allocation; its quality is judged by its aggregate criterion vector using the paper’s criterion orders and priority relations.
My lead is Cohort G-Preferred Configuration, mirroring Theorem 3, proved in this paper. The theorem states that Algorithm Pareto-PBS1 always terminates; every successful run returns a G-preferred solution; and every G-preferred solution is returned by exactly one successful run. The continuous problem is: given the supported types and masses, their CSPs, criterion functions and orders, and the preferences between criteria, compute the exact set of G-preferred mass allocations. Because that set may contain infinitely many allocations, a continuous solver should return a finite symbolic description—such as a rational linear-inequality description of the preferred allocations—with an allocation witness for each represented outcome. “G-preferred” here means the paper’s Definition 4 applied to the aggregate vectors \(z(y)\): no other feasible mass allocation improves the criteria in the way that definition permits.
A second, narrower question is Cohort B-Extreme Configuration, mirroring Theorem 2, also proved here. Theorem 2 states that Algorithm Extreme-PBS1 always terminates; every successful run returns a B-preferred solution; and every B-preferred solution is returned by exactly one successful run. Its continuous counterpart asks for the exact set of allocations lexicographically optimal under at least one ordering of criteria that respects the specified priority relation. A suitable output is the union of the corresponding allocation faces, with their aggregate criterion vectors. This is less ambitious than the lead question: it captures the paper’s extreme-solution computation, while Theorem 3’s G-preferred solutions cover its more general Pareto-oriented search.
For either problem, I would expect the combinatorial difficulty to remain when each type’s CSP is given compactly: a single criterion optimized at mass one can still require finding an optimal feasible configuration. That is a likely Class B boundary, not a hardness result proved by this paper. If feasible configurations are listed explicitly, the mass-allocation model instead becomes a linear optimization problem; its pricing step is where a useful tractability result could emerge. For the full G-preferred set, the size of an exact description is an additional question: even when a preferred allocation is easy to find, the frontier may require a large output.
The mirror covers cohort-level extreme and G-preferred configuration, not every result in the paper. It does not claim that the authors’ search algorithms extend unchanged to mass allocations, or that their preference-projection theorem automatically holds for cohort averages. Further questions include the complexity of pricing over implicitly represented CSPs, whether the G-preferred frontier has a compact description for fixed numbers of criteria, and how the continuous allocations relate to finite cohorts with indivisible headcounts.
The weakest point is the change in decision setting. Junker studies one CSP solution at a time; this mirror chooses a distribution of configurations across a cohort, judged by cohort-wide criteria. That is a meaningful population-level configuration problem, and the paper’s large-catalog motivation makes it recognizable as an extension of its subject. But the paper does not itself make that extension, and its theorems provide algorithmic correctness rather than the complexity anchors the programme most wants.
The strongest objection is that the two anchors establish correctness and completeness of finite search procedures, not computational complexity. Theorem 2 says Extreme-PBS1 returns exactly the B-preferred solutions; Theorem 3 says the same for Pareto-PBS1 and G-preferred solutions. Neither gives a running-time bound or a complexity classification. So a cohort version could pose a new computational question, but it would not carry over a complexity result from this paper.
For Theorem 2, the proposed cohort mirror changes what counts as a solution. The paper’s B-preferred solutions are assignments to the decision variables of one CSP. A cohort model instead chooses how much mass receives each configuration, then applies the criteria and priorities to cohort-wide totals or averages. Those aggregates require a substantive choice about how individuals’ price, quality, and distance should be combined. The paper supplies a way to balance criteria for one vacation; it gives no account of balancing them across customers.
Theorem 3 has the same gap, made sharper by its coverage claim. In a cohort allocation model, there can be continuously many allocations with the same aggregate criterion vector. Enumerating each G-preferred allocation, as the theorem’s finite “exactly one successful run” formulation suggests, is no longer a suitable output. One could ask for a symbolic description of the aggregate frontier instead, but that is a different output problem. If configurations are explicit, the allocation model is a linear optimization problem; if they are implicit, optimization calls back into the original CSP search. Either way, the continuous model needs its own complexity question and justification.
There is a plausible stronger story: a platform serves many recurring customers with the same finite set of profile types, and chooses packages to balance average price and quality. That is a coherent population problem. Its weakness as a mirror is that it adds a social planner’s aggregation objective to a paper about finding preferred solutions for a single decision-maker. If each customer’s criteria are handled separately, the problem tends to decompose by type. If criteria are combined across customers, the model needs new assumptions about whose outcomes can be traded off and how. The paper does not motivate those assumptions.
Theorem 4’s preference-projection result offers a nearby computational hook, but it too concerns search decisions inside one CSP. In a cohort model, the useful analogue would be the marginal value of assigning a small amount of mass to a configuration—a pricing calculation for the new allocation problem. That may be useful machinery; it does not supply a population question from the paper’s result.
I would therefore argue against prioritizing this paper as a ChoCo mirror: the cohort extension is recognizable, but its central modeling choice and computational object come from outside the paper, while its named theorems offer no complexity result to carry over. I cannot honestly rule out every worthwhile scenario. A large configuration service with shared cohort constraints could make the extension valuable; the negative case is strongest as a claim of weak fit, not universal impossibility.
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.