| paper | d4-conf-sagt-2022-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}\)-complete, even for every fixed \(\ell\ge 2\), equal dyadic masses, and at most three approved partners per type per layer. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a bipartite support \(\mathcal T=R\mathbin{\dot\cup}S\), rational masses \(\mu_t>0\) summing to \(1\), and mutually approved type-pair sets \(E_i\subseteq R\times S\) for each layer \(i\in[\ell]\), does there exist a mass matching \(x_{tu}\ge0\) with incident mass at each type at most \(\mu_t\), such that for every \((t,u)\in E_i\) and every layer \(i\), \(h_t^{(i)}h_u^{(i)}=0\), where \(h_t^{(i)}=\mu_t-\sum_{u:(t,u)\in E_i}x_{tu}\) (and symmetrically for \(u\))?
A society is a rational mass distribution over complete approval-profile types on two sides. A decision variable \(x_{tu}\) gives the mass paired across each type pair; the question is whether such a matching exists with no mutually approving type pair having positive unhappy mass at both ends in any layer.
This mirrors only Theorem 1’s symmetric bipartite branch for All-Layers Weak Stability; it does not cover the asymmetric branch or the paper’s other stability notions and parameterized results.
My lead is a mass version of All-Layers Weak Stability, mirroring the symmetric bipartite branch of Theorem 1.
Consider a large two-role matching market, such as tutors and learners, where people share a small number of qualification and availability profiles. A type records a person’s role and their complete approval profile over the other types in each layer. For example, layers might represent weekdays or compatibility criteria. The regime is many people but relatively few types; people of a type are interchangeable for everything the matching problem uses.
Let the support be \(\mathcal T=R\mathbin{\dot\cup}S\), with rational masses \(\mu_t>0\) summing to \(1\). In layer \(i\), let \(E_i\subseteq R\times S\) be the mutually approved type pairs. A solution is a mass matching \(x_{tu}\ge 0\), for every \(t\in R,u\in S\), with total matched mass at each type at most its population mass. Pairings need not be approved. Define \(h_t^{(i)}=\mu_t-\sum_{u:\{t,u\}\in E_i}x_{tu}\): the mass of type \(t\) unmatched or paired with someone it does not approve in layer \(i\). The mass matching is stable in every layer exactly when \(h_t^{(i)}h_u^{(i)}=0\) for every \(\{t,u\}\in E_i\) and every \(i\). In other words, each mutually approving type pair has at least one endpoint whose members are all happy in that layer. This is almost-everywhere pairwise stability: positive unhappy mass at both ends gives blocking pairs. It does not replace a pairwise deviation with a coalition. There is no objective; the question is whether such a mass matching exists.
The anchor is Theorem 1, proved in this paper. It says that for every \(\ell\ge2\), All-Layers Weak Stability is NP-hard both for symmetric bipartite approvals and for asymmetric bipartite approvals in which agents on one side have identical approval sets in the first two layers. Both hardness results hold even when every agent approves at most three agents per layer. The proof reduces from a bounded-occurrence 3-SAT variant and extends the construction to more layers. My mirror covers the symmetric bipartite problem; it does not claim to mirror the theorem’s asymmetric branch.
There is a useful exact bridge for this bipartite mass model. For rational masses, clear denominators to obtain integer counts of clones of each type, with complete approval between type pairs in \(E_i\). A finite matching gives a mass matching by normalizing its pair counts. Conversely, from a mass solution, take \(H_i\) to be the types with zero unhappy mass in layer \(i\). Stability makes \(H_i\) a vertex cover of \(E_i\). Fixing these sets restricts which type pairs may carry matched mass and which types must be fully matched; what remains is a capacitated bipartite flow. With integer clone counts, that flow has an integral solution. Thus the mass solution can be rounded to a matching in the corresponding typed clone market.
That bridge also transfers the theorem’s worst-case hardness: give each source agent its own type, mass \(1/n\), and the same layer approvals. The bipartite flow argument makes the mass instance a yes-instance exactly when the original instance is. So my expected unrestricted classification is hardness transfers (Class B). The high-multiplicity regime has a different useful feature: enumerate, for each layer, the set \(H_i\) of fully happy types, then solve the resulting flow. This gives an exact \(2^{\tau\ell}\operatorname{poly}(\tau,\ell,L)\)-time algorithm, where \(\tau=|\mathcal T|\) and \(L\) is the mass encoding length. Population size drops out; whether the dependence on support can be made polynomial is a further question.
The soft spot is the regime behind the hardness transfer. With one type per source agent, support equals population size. A large market with few types imposes complete type-to-type approval blocks; Theorem 1’s degree-three bound counts named agents, so it does not establish hardness when each person approves a few large categories. The authors should recognize the mass problem as their stability question in the compatibility and attribute setting they discuss, but the theorem alone does not settle the complexity of that specific high-multiplicity regime.
I can’t honestly defeat the anchor. Theorem 1 is a named computational result, and its symmetric bipartite branch has a sensible stronger mirror: a large two-role market in which people share a small number of complete compatibility profiles, with layers for days or qualifications. A mass matching records how much of each type is paired with each other type. For a mutually approving type pair, positive unhappy mass at both ends supplies an actual blocking pair; if either end has zero unhappy mass, that pair cannot block. With types defined by the full profiles the problem uses, this is a coherent population model, not a loss of individual information.
The strongest objection is narrower: the theorem’s reduction can use one type per person, so it establishes hardness when support grows with the market. It does not establish hardness when the population is large but support is small. That is a real gap in what the paper’s result tells us about the intended high-multiplicity regime. But it does not defeat the mirror: finding out whether hardness persists as a function of support is a well-posed computational question. The paper’s parameterized results for few agent types make that regime more plausible, not less.
The proposed clone-and-flow bridge also appears to give the mirror a precise connection to the finite problem, provided its integrality argument is made explicit for the simultaneous layer constraints. The mirror may turn out to be hard only when support is large, or tractable for small support; either answer is useful under this programme. My negative case is therefore weak: I see a limitation in what Theorem 1 proves about low support, but no honest basis for claiming that no worthwhile continuous mirror exists.
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.