| paper | d4-conf-aaai-2018-0294 |
| 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: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Given \(n\) binary product attributes and a support \(S\subseteq\{0,1\}^n\) of size \(\tau\), with positive rational masses \(\mu_o\) summing to \(1\) that represent the fractions of a one-purchase customer cohort selecting each configuration, find a complete linear LP-tree \(L\) minimizing \(R_\mu(L)=2^{-n}\sum_{o\in S}\mu_o\,\operatorname{rank}(L,o)\).
Types are customers grouped by the single configuration they selected; each type carries its fraction \(\mu_o\) of the cohort. The decision is a complete linear LP-tree, and the objective is the cohort’s mass-weighted normalized mean rank of its selected configurations.
Covers Proposition 3’s exact optimization of empirical mean rank for binary linear LP-trees, with sample frequencies replaced by rational cohort masses; it leaves conditional-tree learning, \(k\)-LP-trees for \(k>1\), pruning, and the empirical recommendation results outside this mirror.
The strongest honest case is narrow: this paper has no named hardness result to anchor a “hardness dissolves” claim. Its best computational anchor is Proposition 3, proved here: for binary attributes, Algorithm 1 restricted to linear LP-trees returns a linear LP-tree minimizing the empirical expected rank over that class. The result is an exact optimization guarantee. The proposition does not itself state a complexity class, but its proof gives a simple polynomial-time method for this case.
A plausible regime is a large customer cohort within one product line and market segment, where the paper’s shared-ground-preference assumption is credible. Many customers may have selected the same configuration from a menu, so the number of customers \(N\) can greatly exceed the number \(\tau\) of distinct configurations observed. For this learning problem, a type can be a completed configuration: the objective uses each customer only through the positive example they contribute. The mass \(\mu_o\) is the fraction of customers who selected configuration \(o\). This matches the paper’s aggregation of sales histories within a cluster.
Here is the mirror I would put to a prover, named Binary Population Mean-Rank LP-Tree Learning. An instance is \(n\) binary attributes and a support set \(S\subseteq\{0,1\}^n\) of size \(\tau\), with positive rational masses \(\mu_o\) summing to \(1\). Find a complete linear LP-tree \(L\)—an ordering of the attributes and a preferred value for each—that minimizes
\[
R_\mu(L)=2^{-n}\sum_{o\in S}\mu_o\,\operatorname{rank}(L,o).
\]
The solution is the tree itself. This is the paper’s empirical mean-rank objective with sample frequencies replaced by rational masses. It is an exact high-multiplicity translation: if the masses have common denominator \(D\), repeating each \(o\) exactly \(D\mu_o\) times produces the corresponding sample \(H\).
For each attribute \(i\), compute \(q_i(b)=\sum_{o:o_i=b}\mu_o\). Prefer a value \(b\) maximizing \(q_i(b)\), then order the attributes by decreasing \(\max_b q_i(b)\). Proposition 3’s rank formula shows why: the contribution of an attribute’s preferred value is weighted by its position in the lexicographic order, with earlier positions receiving larger weights. This solves the mirror exactly using polynomially many rational operations in \(n\), \(\tau\), and the input bit length. Its expected fate is tractable. Proposition 3 is proved in the paper; the weighted version follows by replacing sample counts with masses.
The authors should recognize this as their problem: the tree class, rankings, and mean-rank objective are unchanged, and the paper’s algorithms already use counts of positive examples. The scope is deliberately just Proposition 3’s binary, linear-tree optimization result. It does not claim to continuize the paper’s richer conditional-tree learning, pruning, or multi-cluster experiments.
The weakest point is that the continuous population is represented by the distribution of customers’ observed configurations, while the learned object is a preference ranking for a cluster. That could be seen as continuizing the sales-history data rather than modeling a population of heterogeneous preference-holding agents. The paper’s shared hidden preference and its use of sales frequencies make this a plausible, though limited, mirror. It is a tractable anchor, not evidence that continuization removes hardness; extensions to conditional or \(k\)-LP-tree mean-rank optimization would be natural next questions.
The best objection is a mismatch between the paper’s data model and ChoCo’s population model. The paper takes a multiset \(H\) of purchased configurations, viewed as samples from a choice distribution \(p_{\check\succ}\) associated with one hidden preference relation. The proposed \(\mu\) over configurations is therefore naturally a distribution over observed outcomes: it makes choice noise continuous, rather than making users’ preference types the population object. To model a population of heterogeneous users directly, one might instead give each type \(\theta\) a preference relation and a choice distribution, then optimize an average such as
\[
\int \sum_o p_\theta(o)\,\operatorname{rank}(L,o)\,d\mu(\theta).
\]
That is a reasonable population problem, but it changes the paper’s setup: the paper neither has those user types as input nor defines its objective as an average over heterogeneous preferences.
This objection defeats the literal interpretation only. A cohort in which each customer makes one purchase gives a better mirror: treat the selected configuration as the complete type for this particular learning objective, and let \(\mu_o\) be the fraction of customers who selected \(o\). Then the paper’s empirical mean rank becomes exactly \(R_\mu(L)\). That interpretation is plausible for the sales-history setting, and the objective does not track customer identities. Calling it an outcome distribution rather than a population distribution is not enough to rule it out: for this objective, the observed configuration is all the algorithm uses about each customer.
Nor does the lack of a named complexity classification dispose of the anchor. Proposition 3 gives an exact optimization result, and its weighted version is immediate. For each attribute \(i\), compute \(q_i(b)=\sum_{o:o_i=b}\mu_o\); choose the more frequent value and order attributes by decreasing \(\max_b q_i(b)\). The rank formula makes this optimal, with running time polynomial in \(n\), support size \(\tau\), and the mass bit length. The result may be a small extension of the paper’s algorithm, but a tractable answer is not grounds for rejecting a well-posed mirror.
So the population-versus-choice distinction is the strongest negative argument, and it shows that this anchor should be framed narrowly. It does not defeat the one-purchase cohort interpretation. I cannot honestly defend the universal claim that no worthwhile continuous mirror exists: this anchor survives a plausible repair, even though it does not establish that the paper’s broader learning programme is naturally population-continuous.
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.