| paper | d4-conf-ecai-2020-0423 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Both preference families are polynomial-time solvable with zero queries under the stated feasible set. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given τ types with rational masses μ_t, costs w_t, contribution vectors a_t∈ℚ_{≥0}^n, and a per-capita budget B, let F={z: 0≤z_t≤μ_t, ∑_t w_tz_t≤B} and y(z)=∑_t z_ta_t. An unknown OWA or 2-additive Choquet preference ω is accessed through pairwise comparison queries, and Θ records the answers. Does there exist an interactive algorithm, polynomial in the input bit length and τ in time and queries, that returns z∈F with max_{z'=z+q(e_u-e_v)∈F, q≥0} max_{ω∈Ω_Θ}[f_ω(y(z'))-f_ω(y(z))]≤δ, whenever such an allocation is attainable?
A high-multiplicity RBLS model with rational type masses μ_t, selected masses z_t, per-capita costs w_t, aggregate objective vector y(z)=∑_t z_ta_t, and an unknown rank-dependent preference elicited by comparisons. Local moves transfer any feasible amount q between two types; the target is an allocation whose worst-case regret against those moves is at most δ.
The polynomial query proof eliminates candidates from a finite neighborhood; the continuous exchange amounts leave open how to bound the queries needed over an interval, and the proponent does not resolve that issue.
fatal: False
The mirror extends RBLS’s local-search guarantee to type-mass allocations, initially for OWA and 2-additive Choquet preferences. It leaves RBGA, general Choquet capacities, and global minimax-regret optimization uncovered.
The strongest mirror I see is a high-multiplicity version of the paper’s RBLS local-search problem. The paper’s only numbered complexity anchor is Proposition 1, proved here: for the multi-objective knapsack problem, both RBLS and RBGA can be implemented to run in polynomial time and ask at most polynomially many preference queries for OWA aggregators and Choquet integrals. This is a resource guarantee for the procedures; it does not say they find a globally optimal solution for those nonlinear preferences. The paper’s local-search branch is the best fit for a continuous mirror because its neighborhoods already represent small changes to a selected set.
A plausible regime is a large public programme choosing which households receive a limited resource, such as energy retrofits. Each household contributes to several objectives—say emissions reduction, cost savings, and access—and has a resource cost. Households with the same complete profile of costs and contributions are one type. There might be hundreds of thousands of households but only dozens of types. The planner’s trade-off between objectives is unknown and represented, as in the paper, by an OWA operator or Choquet integral.
Here is a concrete continuous question, High-Multiplicity Rank-Dependent Knapsack Local Search. An instance gives \(\tau\) types, with rational population shares \(\mu_t\), costs \(w_t\), and contribution vectors \(a_t\in\mathbb{Q}_{\ge0}^n\). An allocation is \(z_t\in[0,\mu_t]\), the share of type \(t\) selected, subject to \(\sum_t w_tz_t\le B\). Its objective vector is \(y(z)=\sum_t z_ta_t\). The planner’s unknown preference parameter \(\omega\) belongs to an OWA or Choquet family; past comparison answers \(\Theta\) define the compatible set \(\Omega_\Theta\). Queries compare the objective vectors of two feasible allocations.
Define a one-exchange neighborhood \(\mathcal{N}(z)\) to contain feasible allocations formed by moving some mass \(q>0\) from one type to another. The task is: using the comparison oracle, return a feasible allocation \(z\) whose worst-case regret against this neighborhood is at most \(\delta\):
\[
\sup_{z'\in\mathcal{N}(z)}\ \max_{\omega\in\Omega_\Theta}
\bigl(f_\omega(y(z'))-f_\omega(y(z))\bigr)\le\delta.
\]
The algorithm should use time and queries polynomial in the input length and \(\tau\) (first for OWA and 2-additive Choquet preferences). The output is a type-mass allocation and its query transcript. This asks about the underlying selection problem, not an encoding.
I expect this local, fixed-objective-count version to be Class A: the type-level feasible set is a rational polytope, there are only \(\tau(\tau-1)\) exchange directions, and along each direction the rank ordering changes at finitely many breakpoints. Those features give a plausible route to continuous optimization and pricing methods. That is a research expectation, not a consequence of Proposition 1. Natural follow-ups are whether the result extends to variable \(n\) and general Choquet capacities, and whether one can solve the global minimax-regret problem over all feasible mass allocations rather than stop at one-exchange local optimality.
The authors could plausibly recognize this as their problem: the alternatives are still knapsack selections, their additive objective vectors and rank-dependent preference model are unchanged, and only repeated identical items are grouped by type. Mass is the fraction of a type selected; each household still receives a binary decision in the finite realization. The continuation is of the selected population, not of the outcomes, preferences, or time.
My weakest point is the gap between their guarantee and the proposed target. Proposition 1 bounds runtime and query count for heuristic procedures; it does not prove global regret quality, and RBLS’s neighborhood is finite in the paper but continuous here. The mirror therefore rests on a sensible high-multiplicity version of their local-search problem, while the continuous local-optimality guarantee remains to be established.
The strongest objection is that Proposition 1’s query bound depends on a finite neighborhood. RBLS applies the Current Solution Strategy to a candidate set \(X^*\); each answer eliminates at least one candidate, giving at most \(|X^*|-1\) queries per step. The proposed mass-transfer neighborhood contains an interval of possible transfer amounts \(q\) along each type pair. Having \(\tau(\tau-1)\) directions does not by itself give a polynomial algorithm for optimizing regret over those intervals or a bound on the number of queries. Rank crossings may partition each direction into finitely many pieces, but the paper proves no corresponding bound for the robust regret envelope and elicitation process. The proponent’s Class A expectation is a research conjecture, not an extension of Proposition 1.
A better mirror could ask for a global minimax-regret solution over all feasible mass allocations. That is a coherent high-multiplicity question, but it moves further from the result being mirrored: Proposition 1 concerns bounded procedures, and RBLS offers no global-quality guarantee. The global version may be worthwhile in its own right; the paper’s result gives little evidence about its tractability or query complexity.
The proposed household scenario itself is plausible. Repeated households with identical costs and objective contributions form sensible types, and selected mass has a clear interpretation as the share receiving a binary intervention. Existing work also provides LP formulations for optimizing Choquet integrals over polyhedra and mixed-integer sets, with experiments on continuous and \(0\)-1 knapsack problems ([Lesca, Minoux, and Perny, 2013](https://doi.org/10.1016/j.dam.2012.07.007)). That work assumes a fixed capacity, so it does not answer the unknown-preference elicitation question. It does, however, make the continuous optimization substrate less distinctive; the mirror’s main new question would be how elicitation behaves over a continuum of allocations.
I cannot make the universal negative case stick. The household model fits the paper’s selectable-item framework, and a continuous RBLS analogue is recognizable. The honest case against is narrower: the submitted local formulation has not inherited Proposition 1’s guarantees, and the stronger global version remains open. That weakens the proponent’s evidence for this anchor, but it does not establish that no worthwhile continuous 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.