| paper | d4-conf-ijcai-2018-0115 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; a conservative bit-complexity bound is \(O(\tau^2(m+1)L^4)\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given two finite distributions \(\mu\) and \(\nu\) over complete LP-tree types with rational masses, compute the exact value \(\Delta(\mu,\nu)=\sum_{T,U}\mu_T\nu_U d_K(T,U)\), where \(d_K(T,U)\) counts outcome pairs on which the two trees disagree.
Each society is a finite support of LP-tree types with rational mass summing to one. The output is the exact cross-society average of pairwise Kendall distances; there is no intervention variable, and outcomes remain discrete.
Covers the pairwise Kendall distance computation in Sections 3–4 and Theorems 1 and 2, aggregated across two societies; it does not cover clustering or finding a representative LP-tree.
The strongest mirror is Cross-Society LP-Tree Disagreement. Take two large cohorts of agents who compare the same combinatorial outcomes, such as customers choosing flights with the same attributes. A type is a complete LP-tree: its attribute importance structure and every conditional preference table must match. This is a plausible high-multiplicity regime when agents use a shared catalogue of preference templates—for example, standardized travel-policy profiles—so the number of agents can be much larger than the number of distinct trees. The mass of a type is the fraction of its cohort using that tree.
Given finite supports of LP-trees with rational masses \(\mu\) and \(\nu\), summing to one in each cohort, ask for the exact cross-cohort disagreement
\[
\Delta(\mu,\nu)=\sum_{T,U}\mu_T\nu_U\,d_K(T,U),
\]
where \(d_K(T,U)\) is the number of outcome pairs on which \(T\) and \(U\) disagree. The solution is the exact rational value of \(\Delta\). There is no intervention variable: this is an evaluation problem, like the paper’s pairwise distance computation. For finite cohorts with \(n_A\) and \(n_B\) agents, it equals \(1/(n_A n_B)\) times the sum of the pairwise distances across the cohorts. Thus mass replaces individual headcounts while preserving the paper’s distance and leaving outcomes discrete.
My anchor is Theorem 2, proved in this paper. It states that LpDis computes the distance between two input LP-trees in polynomial time, with a quadratic running time in the size of those inputs. Theorem 1, also proved here, supplies the correctness guarantee: LpDis returns the total number of disagreeing outcome pairs. There is no comparable named hardness result in this paper, so the algorithmic anchor is the appropriate one. Run LpDis for each supported pair \((T,U)\), then sum the results with their rational weights. That takes \(\tau_A\tau_B\) distance computations, plus polynomial-time exact rational arithmetic in the mass bit lengths. The resulting mirror is therefore expected to be Class A: tractable.
The authors would likely recognize this as a population-level extension of their problem: they motivate the distance for clustering agents, and this asks for the mean distance between two populations of those agents. The mirror covers the pairwise Kendall distance calculation in Sections 3–4 and Theorems 1 and 2. It does not claim that the paper solves clustering itself. A natural further question is to find an LP-tree that minimizes its average distance to a continuous society, extending the pairwise metric toward a population representative.
The weakest point is that the society-level computation is a weighted aggregation of the authors’ pairwise primitive, rather than a new optimization problem. Its usefulness also depends on a real regime with many agents but relatively few *exact* LP-tree types; if nearly every agent needs a different tree, the support offers little compression. The standardized-template scenario makes that assumption credible in some settings, and the paper’s clustering motivation makes the aggregation recognizable, but it does not make the mirror universal.
The strongest objection is that the proposed mirror adds a population statistic, not a new computational challenge: once LpDis computes \(d_K(T,U)\), the cross-society value is just a weighted sum over supported type pairs. A richer version—such as finding a representative LP-tree or clustering a continuous society—would pose an optimization problem, but it would go beyond Theorem 2 and need a separate justification as a mirror of this paper’s result.
That is a thin case. The weighted mean is still a well-posed computational question about a distribution over complete preference types, and the paper’s clustering motivation makes it recognizable. Standardized LP-tree templates also give a plausible high-multiplicity regime. I see no sound basis here to claim that no worthwhile continuous mirror exists; the negative case rests mainly on the mirror being modest, which is not enough to defeat it under the programme’s criteria.
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.