| paper | d4-conf-ecai-2025-0646 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: The finite decision problem is \(\mathrm{NP}\)-complete. For the specified atomless kernels, \(D_\infty=1/8\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 4.1
statement extracted from the paper’s text layer
Given finite type sets \(I,J\), rational mass distributions \(a,b\), rational tournament kernels \(W,U\) with \(W_{ii'}+W_{i'i}=1\) and \(U_{jj'}+U_{j'j}=1\), and a rational threshold \(\epsilon\), decide whether there is a coupling \(\pi\) with marginals \(a,b\) such that \(\frac12\sum_{i,i',j,j'}\pi_{ij}\pi_{i'j'}|W_{ii'}-U_{jj'}|\le\epsilon\). For the continuous ordered and cyclic kernels corresponding to \(T_{\Ord}\) and \(T_{\Rps}\), determine whether the minimum equals the normalized limit \(1/8\) from Proposition 4.1 or is smaller under fractional couplings.
Represent a continuum of players by finitely many types carrying rational masses, with pairwise win probabilities encoded by tournament kernels. Compare two such populations by minimizing integrated pairwise disagreement over mass-preserving couplings.
The mirror extends the paper’s GED distance, with Proposition 4.1’s ordered and RPS tournaments as a benchmark. It leaves Katz distance, map construction and distortion, and the winner-determination experiments untouched.
There is no qualifying anchor under your rule. The only numbered theorem-like result in the paper is Proposition 4.1: for odd \(n\), the graph edit distance between \(T_{\Ord}\) and \(T_{\Rps}\) is \((n^2-1)/8\). The paper states this as its own proposition, but it is a distance formula, not a result that classifies a computational problem as hard or tractable. The NP-hardness claims for GED and Slater winner determination appear in prose with citations; the polynomial-time claim for Katz distance is also unnumbered. So I cannot honestly supply a continuous problem *per qualifying anchor*.
The strongest positive lead, if the prose GED claim were allowed as an anchor, would be a continuous tournament edit-distance problem. An instance would give two finite sets of player types, rational masses \(a_i,b_j\), and type-level win-probability kernels \(W,U\), with \(W_{ii'}+W_{i'i}=1\) and likewise for \(U\). A solution is a coupling \(\pi\) of the two mass distributions minimizing
\[
\Delta(\pi)=\frac12\sum_{i,i',j,j'}\pi_{ij}\pi_{i'j'}\lvert W_{ii'}-U_{jj'}\rvert.
\]
The decision version asks whether some coupling achieves \(\Delta(\pi)\le\epsilon\), for rational \(\epsilon\). The coupling represents how much mass of each player type is matched to each type in the other tournament; the objective is their integrated pairwise disagreement.
A plausible regime is a very large league whose participants fall into relatively few stable playing-style or strength classes, with pairwise outcomes represented by win probabilities. Then the participant population is continuous while the type support stays small. This is recognizable as an extension of the paper’s isomorphism-invariant GED, and its footnote explicitly mentions weighted tournament graphs. I would tentatively expect continuum-specific hardness (Class C): the optimization is quadratic over a coupling polytope, so it does not immediately become the LP one might hope for. Whether the fractional coupling instead makes the problem tractable is an open question; so are the size of the gap from finite GED and the conditions under which type-level kernels preserve useful tournament structure.
The soft spot is substantial: weighted, exchangeable type-level outcomes change the paper’s deterministic tournament model, and its actual datasets have only \(7\)–\(30\) players. If types must encode enough detail to retain every realized head-to-head result, their number may grow with the population and the compression disappears. This is a plausible extension of the paper’s central distance problem, but it is not a compliant anchor-based case as the prompt stands.
The cleanest case against a mirror is that the paper has no eligible computational result to anchor one. Proposition 4.1 gives a formula for the distance between two particular tournaments; it does not classify a computational problem. GED’s NP-hardness and Slater winner determination’s NP-hardness are cited in background prose, while Katz’s polynomial computation and the ILP experiments are methods and measurements. None is a numbered result of this paper about complexity or an algorithm. Under the requested anchor-based standard, there is therefore nothing here for a continuous question to mirror.
The proposed continuous GED is the strongest lead, and it deserves a direct answer. It is well motivated: with equal atomic masses and a permutation coupling, its objective recovers normalized GED. But its high-multiplicity version has to choose between retaining the realized tournament and replacing it with a weighted kernel. To retain the realized pairwise results, types must encode enough of each player’s outcome pattern that their number will generally grow with the tournament. If a fixed set of player types instead uses type-level win probabilities, the input becomes a weighted, stochastic tournament, and the objective measures expected disagreement under a fractional coupling. That is a coherent graphon-style distance, but it is a new problem about probabilistic tournament kernels, rather than a complexity result from this paper about deterministic tournament distance.
The paper’s election dataset suggests another tempting route: represent voters by a distribution over rankings, derive the majority tournament, then study its map location or its Slater winners. But once the majority tournament is formed, the paper’s downstream computations are unchanged; the population distribution supplies their input without making them population-computational questions. Asking how much voter mass must change to alter the tournament or its map location would add a new intervention objective that the paper does not study.
So I would vote against a *paper-anchored* continuous mirror. The broader claim that no worthwhile mirror exists in any scenario is less secure: the authors themselves call weighted tournaments natural, and their interest in distances across tournament sizes makes a continuous kernel distance a plausible research direction. I can rule out that proposal as an anchor to a computational result in this paper; I cannot honestly rule it out as a potentially worthwhile extension.
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.