| paper | d4-conf-ecai-2025-0549 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
For an atomless probability space \((X,\nu)\) with a bounded-degree, port-labelled treeing, a finite type set \(T\), and rational type masses \(\mu_t=\nu(\{x:\theta(x)=t\})\), can one construct a measurable matching \(M\) along treeing edges such that the set of 1-blocking edges has measure zero? The computational version asks for an algorithm under a fixed effective finite-presentation model for the treeing and matching.
Use a typed measured graph \((X,\nu,\mathcal G,\theta)\): the type masses \(\mu_t\) describe the population, while \(\mathcal G\) preserves the tree-like feasibility constraints. The decision variable is a measurable matching involution along graph edges; the objective is feasibility, with no positive-measure set of blocking edges.
The proposed finite descriptions do not specify an effective encoding of the measure-preserving edge maps, so a polynomial-time construction and its complexity are not yet well defined.
fatal: False
The mirror covers Theorem 4's 1-stability guarantee on acyclic graphs. It leaves Theorems 1–3 on general graphs and Theorem 5's finite convergence bound untouched.
The strongest positive mirror I believe is built around Theorem 4, proved in this paper. It says that on an acyclic acceptability graph, every sequence of 1-blocking moves terminates in polynomially many moves, and each agent participates in at most \(|N|^2/4\) moves. The paper also derives a total bound of \(|N|^3/8\). Since a blocking pair can be found by scanning the listed edges, this gives a polynomial-time way to reach a stable matching from any starting matching. This is an algorithmic anchor, though the paper does not establish a named NP-hardness or other standard complexity classification.
A plausible regime is a very large robot network whose communication structure is tree-like and whose robots repeat a small number of local roles. A type records a robot’s capabilities, its local role and ports, and its strict ranking of those ports. The population grows while the number \(\tau\) of such types stays small. The mass \(\mu_t\) is the fraction of robots of role \(t\). This is high multiplicity because the matching problem uses the shared role-based preferences, not each robot’s name.
The continuous question I would hand to a prover is Stable Matching in a Typed Treeing. An instance consists of an atomless probability space \((X,\nu)\), a finite type set \(T\) with rational masses \(\mu_t\), and a bounded-degree, port-labelled treeing of \(X\): a measurable network whose components are trees, with a finite description by measure-preserving edge maps. Each type specifies a strict ranking of its incident ports, with being unmatched last. Does there exist a measurable matching \(M\), where each \(x\in X\) is either unmatched or paired with an adjacent point and \(M(M(x))=x\), such that the set of 1-blocking edges has measure zero? A solution is such a matching. The algorithmic version asks for a construction from the finite description, with complexity measured in its encoding size, \(\tau\), and the degree bound.
I expect this to be tractable, as a conjectural extension of the paper’s acyclic-graph result: the same local improvement structure may yield a measurable stable matching. The mirror covers Theorem 4’s exact-stability result on acyclic graphs; it does not try to continuize all the paper’s results. The authors could plausibly recognize the problem: the population is the continuous object, and the local network and preference structure needed for matching are retained.
The soft spot is substantial. Type masses alone do not describe who can meet whom, so the mirror must include the treeing as well as \(\mu\). And Theorem 4’s finite polynomial move bound does not itself transfer: in an atomless population, improving moves might continue indefinitely or converge through ever smaller masses. That is the open question the mirror creates. This remains a credible case because the added topology preserves the paper’s defining constraint on feasible matches, while the repeated local roles give a genuine large-population, few-types regime.
The proponent chose the paper’s strongest anchor. Theorem 4 gives a real algorithmic result: from any starting matching on a finite acyclic acceptability graph, every sequence of 1-blocking moves terminates, with a polynomial bound on the number of moves. Scanning the edges to find a blocking pair turns that into a polynomial-time algorithm. So the objection cannot be that the paper has no computational result to mirror.
My concern is that the proposed robot types do not capture the input that result needs. Type masses record how many robots have each role, port structure, and preference order. Stability still depends on which particular robots are adjacent and how the matching sits on that network. The type distribution cannot recover those relationships. Keeping the treeing as a separate input repairs the model, but now the algorithm must read and produce a matching for a represented network. Its complexity depends on how the edge maps are encoded and how the measurable matching is represented; the finite \(O(n^3)\) move bound says nothing about that cost.
That exposes the strongest version of the mirror: ask whether a measurable stable matching can be constructed for a specified class of finitely presented treeings. This is a coherent question, but its core difficulty is measurable matching on an infinite graph, not compression of a large society into type masses. Work on measurable matchings in acyclic Borel graphs shows that representability itself can have structural obstacles; it does not settle preference stability, but it illustrates why the graphing needs its own theory and input model ([Conley and Miller, “Measurable perfect matchings for acyclic locally countable Borel graphs”](https://www.math.cmu.edu/users/math/clintonc/onlinepapers/matching.pdf)). If the question asks only whether a stable matching exists, the finite-tree analogue already has a yes answer for every instance. The new issue is whether that answer can be realized measurably and computed from the chosen representation.
A dense-graph mirror has a related difficulty. The paper’s strict ranks compare named neighbors. A fixed number of high-multiplicity types cannot preserve those rankings as the population grows, unless types encode identities or the model changes to preferences over types, with ties and normalized rank gains. That latter model may be sensible, but it requires more than extending Theorem 4’s typed-tree proposal.
So the negative case is that the treeing mirror has no specified computational representation yet, and the paper’s finite convergence guarantee does not provide one. That is a reason to resist treating this as a ready ChoCo target. It does not establish that no worthwhile mirror exists: a carefully chosen computable class of treeings could make the question valuable. My case against the universal claim is therefore weak at exactly that point.
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.