MatchXplain: Analyzing Preferences, Explaining Outcomes, and Simplifying Decisions

The paper contains no numbered Theorem, Lemma, Corollary, or Proposition asserting a computational result. Its APX-hardness and \(3/2\)-approximation statements are attributed to prior work, while the algorithms are implemented rather than proved. The proposed cohort question is plausible, but it cannot repair the absence of a qualifying computational anchor in this paper.

The objection that survived

The proposed question is sourced only from cited prior work, and its mass-level blocking condition permits fractional splitting that changes the discrete problem's semantics.

What the mirror covers

The proposed mirror covers only maximum-cardinality stable matching with ties and incomplete lists; it leaves the implemented DA, Irving, Király, and TTC mechanisms, Borda and Kendall-τ analytics, PCA, Louvain clustering, tie ratio, and visualizations without an anchor-backed continuization.

Open questions for a prover

The case FOR (proponent)

On the printed paper, there is no qualifying anchor. It contains no numbered Theorem, Lemma, Corollary, or Proposition asserting a computational classification, and it proves no such result. Its closest computational statement is the unnumbered claim in Section 3.2 that maximum-cardinality stable marriage with incomplete preferences and ties is APX-hard, attributed to McDermid (2009); the \(3/2\)-approximation is likewise attributed to Király (2013). Both are prior results, not results proved or formally numbered here. Under the programme’s source rule, that means this paper has no valid anchor-backed positive case.

The strongest conditional mirror would nevertheless be a cohort version of that cited problem. Call it Continuous Maximum Weakly Stable Matching with Ties and Incomplete Lists. Let \(P\) and \(Q\) be finite sets of applicant and position types, with rational masses \(\mu_p\) and \(\nu_q\). Each type has a weak preference order over the opposite-side types, with unacceptable partners below being unmatched. A solution is a nonnegative mass matrix \(x_{p,q}\) satisfying \(\sum_q x_{p,q}\le\mu_p\) and \(\sum_p x_{p,q}\le\nu_q\). It is weakly stable if no acceptable pair \((p,q)\) has positive mass on both sides who would strictly prefer one another to their current partners. The objective is to maximize \(\sum_{p,q}x_{p,q}\), or decide whether a stable matching of mass at least \(K\) exists.

The regime is a large recurring labour or placement market: many applicants and one-to-one positions arrive in cohorts sharing all relevant preferences, acceptability constraints, and other attributes, with \(\tau=|P|+|Q|\ll N\). Clearing denominators gives a finite market of clones, so the model has a genuine rational high-multiplicity interpretation. It preserves the paper’s matching size, ties, incomplete lists, and blocking-pair semantics; it is not merely fractionalizing an unrelated outcome.

I would expect the bounded-type version to be a plausible Class A problem, perhaps reducible to capacitated flow or configuration optimization. For unrestricted \(\tau\), Class B remains possible if the APX-hardness can be encoded in the type agenda while every type has large mass. The key follow-up is whether the cited approximation gap survives this clone-equivalent cohort restriction.

The weakness is substantial: the original hardness may depend on named-agent identity. In the mass model, a cohort can split across several partner types, which an individual cannot do. Thus this is an author-recognizable extension, but not demonstrably a direct mirror of McDermid’s result. I would present it as a promising conditional research question, not as a positive verdict on MatchXplain itself.

The case AGAINST (opponent, writing after the proponent)

The decisive negative point is that this paper has no qualifying computational anchor. It is a demonstration paper, not a complexity paper: it contains no numbered theorem, lemma, corollary, or proposition asserting a computational result. The APX-hardness of maximum stable marriage with ties and incomplete lists, and Király’s \(3/2\)-approximation, are cited results from other papers. DA, TTC, Irving’s algorithms, and Király’s algorithm are implemented, not analysed here. The Borda, Kendall-tau, PCA, Louvain, and tie-ratio components are descriptive analytics, not complexity results.

Thus the proposed continuous maximum-stable-matching problem is not a mirror of a result in MatchXplain. It is a new problem extracted from the bibliography. Under the programme’s source rule, that should not count as an anchor.

Even considered independently, the proposed mirror has a serious faithfulness problem. If \(\mu_p\) and \(\nu_q\) are rational cohort masses and the model is meant to represent cloned finite agents exactly, then a matching matrix must satisfy integrality conditions such as \(N x_{p,q}\in\mathbb{Z}\) after clearing denominators. The resulting problem is a finite high-multiplicity market, not genuinely continuous. If instead \(x_{p,q}\) is allowed to be real, cohorts can be split fractionally across partner types, and the model no longer preserves the discrete stable-marriage problem whose APX-hardness was cited.

Stability also changes substantively. In the paper, weak stability forbids an individual blocking pair. In a nonatomic model, an individual has zero mass. The natural replacement must forbid positive-mass blocking exchanges: for every type pair \((p,q)\), either the mass of \(p\)-agents assigned below \(q\) or the mass of \(q\)-agents assigned below \(p\) must be zero. That is a legitimate new notion, but it is not merely the paper’s stability condition on a larger population. It changes individual justified envy into a mass-level condition and loses precisely the identity-sensitive information that MatchXplain’s explanations display.

The cohort story—graduates and jobs sharing preferences and acceptability constraints—is plausible. That is the strongest point for the other side, and I would not dismiss it by misusing high-multiplicity prior work as a novelty objection. But it supports a separate paper on continuous or high-multiplicity stable matching, not a continuous mirror of MatchXplain’s own results. The universal modelling claim that no such project could ever be worthwhile would be overstated; the source-level conclusion is stronger and cleaner: this paper supplies no result for ChoCo to continuize.

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.