| paper | d4-conf-wine-2018-0032 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: Additive approximation is $\mathrm{NP}$-hard even for $\varepsilon=1/(2m^2)$, uniform dyadic masses, and any fixed rational promise bound $\delta\in(0,1)$. The requested polynomial-time algorithm would imply $\mathrm P=\mathrm{NP}$. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 12
Given finite type sets \(T\) and \(S\), rational masses \(\mu_t\) and \(\nu_s\) summing to one on each side, a strict weak order for each type over opposite-side types, a missing-information bound \(\delta\), and rational \(\varepsilon>0\), what is the complexity of computing a feasible mass-matching matrix \(x\) whose objective is within additive \(\varepsilon\) of the minimum? Feasibility requires \(\sum_s x_{ts}=\mu_t\) and \(\sum_t x_{ts}=\nu_s\); the objective is \(Q(x)=\sum_{t,s} A_{ts}(x)B_{st}(x)\), where \(A_{ts}(x)=\sum_{r:\,s\succeq_t r}x_{tr}\) and \(B_{st}(x)=\sum_{q:\,t\succeq_s q}x_{qs}\).
An atomless two-sided market with unit mass on each side, represented by finite supports \(T,S\) and rational type masses \(\mu,\nu\). Each type has a strict weak order over opposite-side types; a feasible transport matrix \(x\) assigns all mass one-to-one in aggregate, while allowing each type’s mass to split across counterpart types. Minimize \(Q(x)=\sum_{t,s}A_{ts}(x)B_{st}(x)\), the density of potential super-blocking pairs under the worst consistent refinements.
The mirror covers the unrestricted minimax blocking objective underlying Theorem 12, measured as a density in the type-mass market. It leaves the paper’s weakly-stable approximation bounds and the auxiliary deletion problem outside its scope.
The convincing regime is a large clearinghouse with many interchangeable participants on each side: for example, a labor market where applicants and positions fall into a modest number of qualification, location, and schedule cohorts, and preferences are over counterpart cohorts. Each cohort has one reported weak order and the same set of possible refinements. There might be millions of applicants and positions but only tens or hundreds of types. A type is the full description relevant to this problem: its side and its reported preference order. Members are still matched one to one; in an atomless population, a cohort can be subdivided to realize a mass allocation.
My lead is Mass Minimax-Blocking Matching. The input is finite type sets \(T\) and \(S\), rational masses \(\mu_t,\nu_s\) summing to one on each side, a strict weak order for each type over opposite-side types, and a missing-information bound \(\delta\). Here \(\delta\) is the average, weighted by type mass, of the fraction of counterpart pairs that each type’s order leaves incomparable. A solution is a nonnegative mass-matching matrix \(x\) with \(\sum_s x_{ts}=\mu_t\) and \(\sum_t x_{ts}=\nu_s\).
For a man type \(t\), let \(A_{ts}(x)=\sum_{r:\,s\succeq_t r}x_{tr}\): the mass of type \(t\) matched to women it would weakly prefer, or find incomparable, to type \(s\). Define \(B_{st}(x)=\sum_{q:\,t\succeq_s q}x_{qs}\) symmetrically. The question is to find a feasible \(x\) minimizing \(Q(x)=\sum_{t,s}A_{ts}(x)B_{st}(x)\). This is the density of potential super-blocking pairs: each eligible mass on one side can pair with each eligible mass on the other. It is also the worst-case blocking-pair count per \(n^2\) in finite markets converging to these type masses, since the allowed refinements can put each assigned partner below the alternatives tied with it. The mass matrix is realizable by partitioning the atomless cohorts into matched pieces.
The hardness anchor is Theorem 12, proved in this paper. It states that for every constant \(\epsilon\in(0,1]\) and every \(\delta\in(0,1)\), unless \(P=NP\), there is no polynomial-time \((n\sqrt{\delta})^{1-\epsilon}\)-approximation for \(\delta\)-min-bp-super-stable-matching, where the instance’s missing information is at most \(\delta\). The theorem is proved by a gap reduction from Vertex Cover. This is the right anchor because it concerns the paper’s unrestricted minimax objective, rather than an auxiliary encoding. The paper’s Theorem 2 supplies the bridge: in its finite model, minimizing super-blocking pairs is equivalent to minimizing the maximum number of blocking pairs over completions.
I expect the mass problem to be Class C—hard for continuum-specific reasons—because \(Q\) is a quadratic objective over a transport polytope, with no apparent linear-programming structure. That is a conjecture about the mirror, not a consequence of Theorem 12. The discrete reduction does not automatically transfer: mass can be split across partners, so its indivisible choices may disappear. A useful programme of work would ask whether the quadratic structure admits a tractable relaxation, whether hardness persists with splittable mass, and how complexity depends on the number of supported types and the input bit length. The mirror covers the unrestricted minimax problem and Theorem 12; it does not claim that the paper’s approximation bounds for weakly-stable matchings carry over.
My weakest point is the change from preferences over named individuals to preferences over counterpart types, together with divisible cohort mass. That changes the feasible matching space, and could erase exactly the combinatorics behind Theorem 12. The case for the mirror is instead that the scenario makes those cohorts genuine equivalence classes, while the objective still asks the authors’ central question: how many pairs can be made to block under the worst consistent refinement of partial preferences?
Theorem 12 is a real computational anchor: it proves an inapproximability result for the paper’s unrestricted minimax objective, and Theorem 2 connects that objective to minimizing super-blocking pairs. So the negative case cannot rest on a lack of a result to mirror.
Its strongest objection is that the theorem’s hard instances are built from named agents with finely arranged, identity-specific preference lists. In Theorem 12’s reduction, the graph vertices and edges are encoded through particular men, women, and cyclic preference gadgets. If types preserve those rankings over named counterparts, the number of types grows with the market; the proposed finite-support high-multiplicity regime has disappeared. If instead counterparts are grouped into cohorts and members of each cohort become tied, as in the proponent’s model, the preferences and blocking structure have changed. The theorem’s reduction then says nothing about the complexity of optimizing \(Q(x)\) as a function of support size and bit length.
That is a substantial mismatch between the theorem and its proposed mirror, but it does not dispose of the mirror. The cohort model is coherent, mass matchings are realizable in an atomless market, and \(Q(x)\) is a natural density of super-blocking pairs. The problem still asks a recognizable version of the paper’s central question. The fact that the reduction may not survive aggregation is not, by itself, a reason the question is unworthy.
I therefore cannot make a strong universal case against a continuous mirror here. The paper supplies a clear computational result, and a plausible large clearinghouse supplies a credible high-multiplicity regime. My negative case is limited to saying that Theorem 12 does not validate the proposed mirror: its hardness depends on identity-level structure that the finite-type model removes. Whether the resulting quadratic mass-matching problem is worth studying remains open, and the material given does not support the claim that no scenario makes it worthwhile.
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.