| paper | d4-conf-atal-2017-0003 |
| 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: \(\mathrm{NP}\text{-complete}\), even with equal dyadic masses on equally sized supports. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given finite type sets \(M\) and \(W\), rational masses \(\mu_i,\nu_j\) summing to one on each side, and complete deterministic pairwise preference relations over opposite-side types that may be cyclic, does there exist a nonnegative flow \(x_{ij}\) with \(\sum_j x_{ij}=\mu_i\) and \(\sum_i x_{ij}=\nu_j\) such that for every pair \(i,j\), \(A_{ij}(x)=\sum_{j':\,j\succ_i j'}x_{ij'}\) and \(B_{ij}(x)=\sum_{i':\,i\succ_j i'}x_{i'j}\) are not both positive?
A two-sided population of preference types with rational mass; \(x_{ij}\) is the mass matched between types \(i\) and \(j\). Each person receives one indivisible partner, while the flow records cohort assignments. Stability means no pair of types has positive mass on both sides who prefer each other to their assigned partners.
Covers Theorem 4's deterministic stable-matching existence question and its hardness. It leaves the uncertain-preference problems of Theorems 2 and 3, Theorem 5's tractability result, and Theorem 8's graph-kernel corollary without a mirror.
The strongest honest lead is Theorem 4: “ExistsCertainlyStableMatching is NP-complete, even if all agents are certain.” The paper proves this result here by reduction from 3-SAT. “Certain” means every pairwise comparison is resolved, while the resulting preferences may still be cyclic. The theorem is therefore about the computational difficulty of finding a stable matching under cyclic preferences, not about computing a probability.
I would mirror it with Stable Mass Matching. The input is two finite sets of types, \(M\) and \(W\), with rational masses \(\mu_i\) and \(\nu_j\) summing to one on each side. Each type specifies a complete, deterministic pairwise preference relation over the types on the opposite side; cycles are allowed. A type describes agents who are identical for everything the problem uses, and partners within a type are interchangeable.
A solution is a nonnegative rational flow \(x_{ij}\), where \(x_{ij}\) is the mass of type \(i\) matched to type \(j\), with
\[
\sum_j x_{ij}=\mu_i
\quad\text{and}\quad
\sum_i x_{ij}=\nu_j.
\]
The question is whether a complete, stable flow exists. For each potential pair of types \(i,j\), define
\[
A_{ij}(x)=\sum_{j':\,j\succ_i j'}x_{ij'}
\quad\text{and}\quad
B_{ij}(x)=\sum_{i':\,i\succ_j i'}x_{i'j}.
\]
The flow is stable if there is no pair \(i,j\) for which both \(A_{ij}(x)>0\) and \(B_{ij}(x)>0\). Those two positive masses could be matched to each other and would each prefer the deviation. Every person still receives one integral partner; \(x\) records how the cohorts are paired.
A plausible setting is a large centralized placement market: for example, graduates and entry-level positions grouped into preference and priority profiles. Suppose there are \(n\) types on each side, with \(q\) otherwise-identical agents in each type. Then the market has \(qn\) agents but only \(2n\) types, and \(q\) can be large. The profile must be complete over partner types, including any pairwise cycles; that assumption fits markets where decisions are specified through pairwise comparisons, though it is less natural if every preference must come from a transitive utility ranking.
The hardness transfer has a concrete basis. On the equal-mass instances corresponding to the paper’s balanced stable-marriage instances, set each type’s mass to \(1/n\). If a stable flow exists, the graph of pairs with \(x_{ij}>0\) has a perfect matching: its fractional matching satisfies Hall’s condition. Any perfect matching chosen from that support is stable. If a type pair blocked that matching, each endpoint would have positive flow to a partner type it ranks lower, contradicting the flow’s stability. Conversely, any stable discrete matching gives a stable flow by putting mass \(1/n\) on each matched pair. Thus, on these instances, a fractional flow exists exactly when the original discrete instance has a stable matching. Theorem 4’s 3-SAT reduction therefore gives this mass problem a direct Class B hardness anchor; fractional cohort assignment does not dissolve the hard case. The number of types grows with the reduction, but the population can be much larger still by replicating each type.
The authors should recognize the mirror’s core: existence of a complete matching with no blocking pair under cyclic, certain preferences. Continuity enters through the population, and the type-to-type flow is the aggregate representation needed to match it. This case covers Theorem 4’s deterministic special case. It does not mirror Theorems 2 or 3, whose “possibly stable” and highest-stability-probability questions depend on independent uncertainty; in an atomless population, defining the probability that no blocking pair exists needs separate care.
The main weakness is the regime’s plausibility. Cyclic preferences are central to Theorem 4’s hardness, and its reduction uses many distinct role profiles. A market that insists on transitive rankings, or has very few types, may not resemble those hard instances. I would still pursue this mirror because the assumptions are explicit, the population can be high-multiplicity, and the support argument gives a precise reason the discrete hardness survives. Further questions include whether the paper’s one-transitive-side tractability boundary extends to mass flows, how unequal type masses affect algorithms, and what a faithful continuous uncertainty model should mean.
There is one anchor to defeat: Theorem 4. The strongest objection is that its agents rank particular people, while the proposed mass flow makes everyone within a type interchangeable. In the theorem’s reduction, those people play distinct gadget roles. If their identity-dependent preferences are preserved in the type definition, the number of types can grow with the population and the high-multiplicity compression disappears. If they are grouped by role instead, the model adds a symmetry assumption absent from the paper.
That objection narrows the mirror, but does not defeat its best version. In a placement market with repeated applicant and position profiles, identities can be irrelevant to the preferences used for stability; the type-level flow is then a natural population model. Replicating each profile makes multiplicity large, and cyclic preferences over profiles preserve the feature Theorem 4 studies. The paper’s one-to-one matching structure also makes the model easier to recognize than a mirror that requires a new notion of outcome or stability. The need to coarsen partners into interchangeable types is a limitation, not a decisive mismatch.
Nor does nearby work on fractional stable matching establish a collision: that literature studies agents receiving fractional or time-sharing assignments, whereas the proposed mirror makes the population continuous while each individual still receives one partner. [Stable Fractional Matchings](https://www.sciencedirect.com/science/article/am/pii/S000437022030165X) and [Fractional Matchings under Preferences: Stability and Optimality](https://www.ijcai.org/proceedings/2021/13) are relevant neighbors, but their fractional-outcome focus does not settle this population-level question.
The adverse case is therefore one of scope and priority: the convincing scenario is narrower than the theorem, and its type symmetry may be a poor fit for markets where individual identities matter. But the mirror survives that objection. Since the brief rules out rejecting a well-posed mirror merely because its answer may transfer from the discrete problem, I cannot honestly argue that no worthwhile scenario exists. The negative case is weak; Theorem 4 remains a credible continuous mirror.
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.