| paper | d4-conf-aaai-2015-0588 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: NP-complete, hence NP-hard, for every fixed \(K\in\{\mathrm{UI\text{-}FP},\mathrm{UI\text{-}UP},\mathrm{UI\text{-}CP}\}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Fix \(K \in \{\mathrm{UI\text{-}FP}, \mathrm{UI\text{-}UP}, \mathrm{UI\text{-}CP}\}\). An instance gives \(p\), a finite support \(E\) of labeled comparisons \(e=(\alpha,\beta,v)\) over \(\{0,1\}^p\), positive binary-rational masses \(\mu_e\) summing to \(1\), and a rational threshold \(q \in [0,1]\). Does there exist a tree \(T \in K\) that satisfies comparisons of total mass at least \(q\), that is, \(\sum_{e \in E:\,T\text{ satisfies }e}\mu_e \ge q\)?
A large survey population has types \(e=(\alpha,\beta,v)\), where each respondent reports one comparison and \(v\) records strict preference or indifference. Type \(e\) has mass \(\mu_e\); the decision variable is a shared tree \(T \in K\), and the objective is to maximize \(\sum_{e:\,T\text{ satisfies }e}\mu_e\).
The mirror covers MAXLEARN for UI-FP, UI-UP, and UI-CP trees; it leaves CONSLEARN, SMALLLEARN, and the CI-tree learning results outside its scope.
The best case is the paper’s MAXLEARN result. Imagine a large preference survey over products or policies described by \(p\) binary issues. Each respondent is shown a pair of outcomes \(\alpha,\beta\in\{0,1\}^p\) and reports either that \(\alpha\) is preferred to \(\beta\), or that they are indifferent. If each respondent contributes one comparison, their complete type for this learning task is \(e=(\alpha,\beta,v)\), where \(v=1\) denotes strict preference and \(v=0\) denotes indifference. The mass \(\mu_e\) is the fraction of respondents with that response. In a large survey, many respondents may repeat the same comparison, so the population size \(n\) can be much larger than the support size \(\tau\). This is a credible high-multiplicity regime for preference elicitation.
My anchor is Theorem 6, which the paper states for UI-FP, UI-UP, and UI-CP PLP-trees. It says that, given a set \(E\) of examples and a target \(k\), deciding whether there is a tree in any one of those classes that correctly satisfies at least \(k\) examples is NP-complete. The paper establishes membership in NP and says the hardness follows by adapting the proof for learning lexicographic strategies by Schmitt and Martignon (2006). In full, satisfaction means that a tree strictly ranks \(\alpha\) above \(\beta\) for an example \((\alpha,\beta,1)\), and makes them equivalent for \((\alpha,\beta,0)\).
I would call the mirror Continuous Maximal UI-PLP Learning. Fix one class \(K\in\{\mathrm{UI\mbox{-}FP},\mathrm{UI\mbox{-}UP},\mathrm{UI\mbox{-}CP}\}\). An instance consists of \(p\), a finite support \(E\) of distinct labeled comparisons \(e=(\alpha,\beta,v)\), positive binary-rational masses \(\mu_e\) summing to \(1\), and a rational threshold \(q\in[0,1]\). Ask whether there is a PLP-tree \(T\in K\) satisfying comparisons of total mass at least \(q\):
\[
\sum_{\{e\in E:\,T\text{ satisfies }e\}}\mu_e\ \geq\ q.
\]
A solution is such a tree. This is the frequency-weighted version of the paper’s maximal-learning problem: it still learns one shared PLP preference model by maximizing agreement with observed comparisons.
I expect this mirror to be NP-complete, with hardness transferring from the paper’s discrete problem. Given an instance with \(m\) examples and target \(k\), assign every example mass \(1/m\) and set \(q=k/m\). The continuous instance then has a qualifying tree exactly when the original instance does. Theorem 6 supplies that result for each of the three UI classes. The natural complexity parameters are \(p,\tau\), and the bit length \(L\) of the masses and threshold. This mirror covers the paper’s MAXLEARN results for UI-FP, UI-UP, and UI-CP; it does not claim a mirror for its other learning problems or the CI classes.
The soft spot is that the population here consists of elicitation responses, not each respondent’s entire latent preference relation. The mirror is strongest in a survey regime where each respondent contributes one comparison, or where each comparison event is the unit being modeled. Then the comparison type fully captures that unit’s contribution to MAXLEARN. If the intended unit is a person whose many judgments must be kept together, the type would need to include that whole bundle, changing the problem. That limitation narrows the scenario, but it does not erase the plausible large-panel regime.
The weighted question also opens follow-up questions: can one approximate the maximum satisfied mass efficiently, and are there exact or parameterized algorithms in \(p\) or \(\tau\)? The hardness embedding gives a clear starting boundary for asking them.
The strongest objection is about what counts as the population. The paper’s examples are training records, not voters with complete preference rankings. If respondents answer many comparison questions, treating each answer as a separate unit gives more influence to people who answer more questions; treating each respondent as a unit changes the problem. And a tree that best fits everyone’s reported comparisons is a learned representative model, not a social choice outcome.
That objection does not defeat the best version of the mirror. A survey can give each respondent one comparison to answer. Then a type \(e=(\alpha,\beta,v)\) completely describes that respondent’s contribution to this learning task, and its mass is the fraction of respondents with that response. The paper’s MAXLEARN objective becomes maximizing the mass of responses the tree satisfies. This is a coherent large-panel regime, and the authors could recognize the weighted problem as their maximal-learning question.
The computational anchor is solid too. Theorem 6 gives NP-completeness for each of UI-FP, UI-UP, and UI-CP. Assigning mass \(1/m\) to each of the \(m\) examples and setting \(q=k/m\) embeds the paper’s decision problem in the mass-weighted one. Rational masses also let the continuous formulation express high multiplicities compactly. That the unweighted case is recovered exactly is not a reason to dismiss the mirror under this programme’s criteria.
So the fit with social choice is debatable: this is preference learning from a population’s reports, rather than choosing among outcomes for that population. But I cannot make that boundary objection strong enough to rule out the mirror, especially given the paper’s focus on preferences and the plausible one-response-per-person scenario. The continuization remains well-posed, computational, and grounded in a named result. The honest negative case is weak; this anchor survives.
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.