| paper | d4-conf-atal-2019-0074 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: Always terminates with a fully evaluated assignment \(x\in\mathcal F\) satisfying \(\Phi_\mu(x)\le w\min_{y\in\mathcal F}\Phi_\mu(y)+\epsilon\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 7.1
statement extracted from the paper’s text layer
Given a finite-domain assignment space \(\mathcal F\), a finite support \(T\) of preference types with rational masses \(\mu_t\ge0\) summing to \(1\), and type-specific nonnegative cost tables with entries that can be elicited for free, let \(F_t(x)\) be type \(t\)'s completed cost and \(\Phi_\mu(x)=\sum_{t\in T}\mu_tF_t(x)\). For inputs \(w\ge1\) and \(\epsilon\ge0\), can DFBnB with a mass-weighted LUC lower bound return a feasible assignment \(x\), eliciting enough entries to evaluate its true cost, with \(\Phi_\mu(x)\le w\min_{y\in\mathcal F}\Phi_\mu(y)+\epsilon\)?
A shared timetable has a finite set of feasible assignments \(\mathcal F\); residents with identical complete cost-table bundles form types with rational masses \(\mu_t\). The decision variable is the timetable assignment \(x\), the objective is per-capita cost \(\Phi_\mu(x)=\sum_t\mu_tF_t(x)\), and unknown type-level table entries can be elicited for free. The question is whether a mass-weighted LUC branch-and-bound search preserves the \(w\)-relative and \(\epsilon\)-additive solution-quality guarantee.
The mirror covers Theorem 7.1's LUC quality guarantee with free elicitation; it leaves Theorems 7.2 and 7.3, the paid-elicitation IWCSP+EC setting, and the experimental comparisons unassessed.
The strongest mirror I see is Theorem 7.1, proved in this paper. It says that depth-first branch-and-bound using the Least Unknown Cost (LUC) heuristic, with relative weight \(w\ge1\) and additive weight \(\epsilon\ge0\), returns an IWCSP solution of cost at most \(w\cdot \mathrm{FP}(x^*)+\epsilon\), where \(x^*\) is an optimal complete IWCSP solution. This result applies when elicitation costs are zero. It is a solution-quality guarantee, not a polynomial-time claim.
A plausible continuous setting is a large organization choosing a shared timetable. The variables are events, their domains are available time slots, and each person’s preference contributes cost factors over those choices. There may be thousands of participants but only a few dozen recurring preference types. A type is the participant’s complete bundle of cost factors, including the actual values behind any entries not yet elicited; people of the same type have identical preferences for every decision the model uses. The mass \(\mu_t\) is the fraction of participants of type \(t\). Eliciting a hidden entry for a type reveals the shared value for that type. This is a population model: the timetable choices remain discrete.
Here is the corresponding problem, which I’d call Continuous High-Multiplicity Incomplete WCSP Approximation. An instance has finite-domain variables \(X\), a known feasible set \(\mathcal F\), and \(\tau\) preference types with rational masses \(\mu_t\ge0\) summing to \(1\). Each type \(t\) has a bundle of nonnegative cost tables, some entries of which are hidden but can be elicited for free. Let \(F_t(x)\) be the total cost of type \(t\)’s bundle at assignment \(x\), and let the true per-capita cost be \(\Phi_\mu(x)=\sum_t\mu_tF_t(x)\). Given \(w\) and \(\epsilon\), the task is to return a complete feasible assignment \(x\), with enough elicited entries to evaluate its cost, such that \(\Phi_\mu(x)\le w\min_{y\in\mathcal F}\Phi_\mu(y)+\epsilon\). The guarantee is judged against the true, completed tables. A mass-weighted LUC lower bound is the natural analogue of the paper’s heuristic.
I expect the quality guarantee to carry over: weighting each type’s costs by its mass changes the objective’s coefficients, and the same lower-bound argument should apply with those weights included. For polynomial-time optimization, however, I expect hardness to transfer. With one type of mass \(1\) and no hidden entries, the model contains ordinary WCSP optimization. That observation is my reduction argument, not a result proved in this paper; Theorem 7.1 itself says nothing about worst-case running time. Further questions include whether bounded treewidth or restricted cost tables yield fixed-parameter algorithms in the continuous model, and whether a useful quality guarantee survives when elicitation costs are charged per unit of population mass.
This mirror covers Theorem 7.1’s free-elicitation result. It does not extend that theorem to the paper’s paid-elicitation IWCSP+EC setting: the paper explicitly says its quality bounds do not apply there. That is also the weakest point. The anchored result is about solution quality, not complexity, and aggregating identical preferences may simply reweight the objective without making search faster. Still, the scenario makes the high-multiplicity question credible: many people can contribute to one shared decision through a small number of complete preference types, which is precisely the population regime the mirror is meant to test.
The sole anchor is Theorem 7.1, but its result is a quality bound for one branch-and-bound heuristic, not a running-time bound or complexity classification. That makes it a weak anchor for ChoCo’s central question: what changes computationally when the population is continuous? The theorem has no population parameter to begin with. It concerns a finite assignment tree and the cost of completing partial assignments; elicitation is free.
The best population version is coherent: a large organization chooses a shared timetable, people with identical complete preference tables form types, and the objective is the average cost \(\Phi_\mu(x)=\sum_t\mu_tF_t(x)\). But for this theorem, those masses simply become coefficients in a weighted WCSP. LUC can use mass-weighted lower bounds, and the proof’s pruning argument carries over with the aggregate objective. The search still ranges over the same timetable assignments, and unknown entries still have to be elicited by type. This is a sensible weighted formulation, but it yields no population-specific algorithmic question anchored by Theorem 7.1; the theorem’s guarantee follows by substituting the weighted costs into the existing argument.
A more consequential version would make elicitation costs accrue across the population, or let nominally identical people have independent hidden preferences. The first leaves the theorem’s free-elicitation setting, where the paper explicitly gives no quality guarantee; the second breaks the shared type-level value that makes a finite-support population model useful. One could still study high-multiplicity IWCSPs as a new complexity problem, but that would be an extension of the model, not a mirror of this theorem.
This is the strongest negative case, and it is not airtight. The timetable scenario makes high multiplicity plausible, and an exact transfer of a known guarantee can still be a useful result. The weakness is that the paper’s named theorem offers little computational structure for continuization to expose: its population analogue appears to be weighted bookkeeping around the same discrete search.
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.