| paper | d4-conf-aaai-2016-0565 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Yes. A deterministic polynomial-time algorithm outputs a feasible binary-encoded rational mass matching with welfare at least \(\frac58\operatorname{OPT}_\mu(d)\) for every consistent metric \(d\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
Given finite types \(T\), positive rational masses \(\mu_t\) summing to \(1\), and strict rankings \(P_t\) of partner types, including same-type partners, promised consistent with a hidden symmetric metric \(d\) on \(T\), is there a randomized algorithm running in time polynomial in \(\tau=|T|\) and input bit length \(L\) that outputs a feasible mass matching \(Y=(y_{tu})\) with \(\mathbb{E}[W_d(Y)]\ge \frac{5}{8}\operatorname{OPT}_\mu(d)\) for every consistent \(d\)? Here \(y_{tu}\ge0\), \(y_{tu}=y_{ut}\), each type satisfies \(\sum_{u\ne t}y_{tu}+2y_{tt}=\mu_t\), welfare is \(W_d(Y)=\sum_{t<u}y_{tu}d(t,u)\), and \(\operatorname{OPT}_\mu(d)\) is the maximum welfare over feasible mass matchings.
A continuum of agents grouped into identical-profile types \(t\in T\), with rational population masses \(\mu_t\), ordinal partner rankings \(P_t\), and hidden metric pair values \(d(t,u)\). The decision variables \(y_{tu}\) specify the mass paired between types, including within-type pairs; the objective is to maximize total hidden metric value while a randomized algorithm uses only the rankings and masses.
The proponents acknowledge that Theorem 3.1 does not establish a polynomial-time aggregation in \(\tau\) and \(L\) for rational masses; whether such an algorithm exists remains the main unproved part of the mirror.
fatal: False
The mirror covers Theorem 3.1's metric maximum weighted matching result. It leaves the general-weight matching, Max \(k\)-Matching, and clustering results outside its scope.
The strongest case is a narrow mirror of the paper’s metric Maximum Weighted Matching result. I would call the continuous problem Metric Ordinal Mass Matching (MOMM).
The lead anchor is Theorem 3.1, proved in this paper. It says that when hidden edge weights satisfy the metric inequality, Algorithm 3 uses only the agents’ rankings and returns a perfect matching whose expected weight is at least \(5/8\) of the maximum possible weight—that is, an ordinal \(8/5\)-approximation. This is the paper’s central result. It offers an approximation anchor rather than a hardness result.
A plausible high-multiplicity setting is a large student population being paired into diverse teams. A type is a shared skill or opinion profile; students of the same type have the same ranking of partner types and the same hidden pair values. The value \(d(t,u)\) of pairing types \(t\) and \(u\) is a symmetric metric distance, and greater distance means greater diversity value. There may be millions of students but only a few hundred profile types. The mass \(\mu_t\) is the fraction of students of type \(t\). This keeps the paper’s objective, hidden metric weights, and ordinal information intact while representing repeated profiles by mass.
Here is the continuous question I would hand to a prover. An instance consists of a finite support \(T\), rational masses \(\mu_t>0\) summing to \(1\), and a ranking \(P_t\) of the other types for each \(t\). The input promises that some symmetric metric \(d\) on \(T\) is consistent with these rankings: if \(t\) ranks \(u\) above \(v\), then \(d(t,u)\ge d(t,v)\). The metric itself is hidden.
A solution pairs the population’s mass. For each unordered pair of types, choose \(y_{tu}\ge0\), where \(y_{tu}\) is the fraction of the population paired across those types; \(y_{tt}\) is the mass of within-type pairs. A perfect mass matching satisfies, for every type \(t\), \( \sum_{u\ne t} y_{tu}+2y_{tt}=\mu_t \). Its welfare under \(d\) is \( W_d(y)=\sum_{t<u}y_{tu}d(t,u) \), since within-type pairings have distance zero. Write \(\operatorname{OPT}_\mu(d)\) for the greatest welfare among feasible mass matchings.
MOMM asks for a randomized algorithm, given only \((T,\mu,P)\), that runs in time polynomial in the support size \(\tau=|T|\) and the input bit length \(L\), and outputs a feasible mass matching \(Y\) such that, for every consistent hidden metric \(d\), \( \mathbb{E}[W_d(Y)]\ge (5/8)\operatorname{OPT}_\mu(d) \). This is the continuous \(8/5\)-approximation question. Individual students still receive one partner; the fractional quantities describe how much of each cohort is paired with each other cohort.
I expect this to be Class A, though the paper does not establish the compressed running time. Its greedy and random construction looks amenable to an aggregate version over the \(\tau\) types, and the proof’s charging arguments may extend to mass. The main follow-up questions are whether that construction can be implemented in time polynomial in \((\tau,L)\) without expanding the population, and whether splitting mass makes a better ordinal approximation possible. The paper’s finite algorithm and its guarantee do not by themselves answer either question.
The authors should recognize this mirror: it is still their metric diversity matching problem, with the same hidden pair values, rankings, and welfare objective. The mirror covers Theorem 3.1’s metric MWM result only; it does not claim to continuize the paper’s general-weight matching, \(k\)-matching, or clustering results.
The weak point is the compression step. The theorem is about named agents, while this question asks for a polynomial-time algorithm on binary-encoded type masses; finite-population parity and the unit-level random choices need a mass-level treatment. That gap is real, but it is also the computational question the mirror puts on the table. The assumption that repeated students really share all relevant interaction values is restrictive; in the stated profile-cohort regime, however, it is exactly what makes the high-multiplicity model sensible.
The strongest negative case is that the paper’s agents are difficult to compress without changing what “same type” means. A person’s type would have to capture their interaction with every possible partner, not just their broad skills or opinions. In many matching settings—especially friendship networks and team formation—those interactions are personal and may not be metric. Grouping people by profile can then discard information that determines the edge weights; keeping enough information to preserve it can make the support size nearly the population size. That makes the proposed high-multiplicity regime narrow in the paper’s motivating applications.
But this does not defeat the best mirror. Diverse-team formation based on shared feature profiles and metric distance is a coherent regime: repeated profiles can be treated as types, and the mass matching remains a meaningful version of the paper’s objective. The strict rankings among individual clones would need a natural weak-order or type-level formulation, but that is a repair, not a fundamental obstruction.
Nor can I dismiss the anchor for lack of a computational result: Theorem 3.1 is a named approximation result. Its mass version would ask whether the guarantee can be obtained in time polynomial in support size and input bit length, so it is a real computational question even if the proof might extend fairly directly.
So the negative case is limited to saying that the mirror fits a specific diversity model better than matching generally, and may offer less novelty if the mass proof is routine. Those points lower its expected payoff; they do not show that no worthwhile scenario exists. I cannot honestly defeat the anchor as stated.
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.