| paper | d4-conf-ijcai-2021-0156 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathsf{NP}\text{-complete}\), even with equal dyadic masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.6
statement extracted from the paper’s text layer
Given finite type supports \(T_L,T_R\), positive rational masses \(\mu_t\) summing to one on each side, satisfaction values \(s_t(u)\), and a welfare threshold \(\Gamma\), is there a nonnegative flow \(x_{tu}\) with \(\sum_u x_{tu}\le\mu_t\) and \(\sum_t x_{tu}\le\mu_u\), such that each type receives a common per-capita mix, \(U_t=\sum_u s_t(u)x_{tu}/\mu_t\), and for every acceptable pair \(t,u\), \(U_t\ge s_t(u)\) or \(U_u\ge s_u(t)\), while \(\sum_{t\in T_L\cup T_R}\mu_tU_t\ge\Gamma\)?
A bipartite market with type masses \(\mu_t\), flow variables \(x_{tu}\), per-capita utilities \(U_t=\sum_u s_t(u)x_{tu}/\mu_t\), and welfare \(\sum_t\mu_tU_t\); each acceptable type pair must have at least one endpoint whose utility meets the satisfaction value of the other.
The paper does not establish that individual cardinally stable matchings can be aggregated into a stable common mix for repeated types; averaging can break the stability disjunctions.
fatal: False
The mirror covers the maximum-welfare cardinal-stability problem anchored by Theorem 5.6. It leaves the ordinal-stability, maximum-fully-matched, approximation, and structural results outside this mirror.
The strongest case is a mirror of the paper’s maximum-welfare cardinally stable matching problem. Imagine a large two-sided job-sharing market with many workers and positions but relatively few complete profiles: workers with the same skills, location, availability, acceptable position types, and satisfaction values; employers with the same role and preferences over worker types. A type includes the market side and the full information the problem uses, not just a job title. Its mass \(\mu_t\) is its fraction of the population. The number of people could be far larger than the number \(\tau\) of supported types.
Here is a precise version, Typed Continuum Max-Welfare CSM. The input is finite supports \(T_L,T_R\), positive rational masses \(\mu_t\) summing to \(1\), a rational satisfaction value \(s_t(u)\ge 0\) for each type \(t\) and opposite-side type \(u\), and a rational welfare threshold \(\Gamma\). Zero satisfaction means the pair is unacceptable. Choose a nonnegative flow \(x_{tu}\), the mass matched between each pair of types, with \(\sum_u x_{tu}\le\mu_t\) for each \(t\in T_L\) and \(\sum_t x_{tu}\le\mu_u\) for each \(u\in T_R\). Require that everyone in a type receives the same per-capita mix of partners. Thus type \(t\)’s utility is \(U_t=\sum_u s_t(u)x_{tu}/\mu_t\), with the analogous formula for a right-side type. For every acceptable pair \(t,u\), require \(U_t\ge s_t(u)\) or \(U_u\ge s_u(t)\); this is exactly the paper’s cardinal no-blocking condition applied to the types’ per-capita utilities. The welfare is \(\sum_t\mu_t U_t\), over both sides. The decision question is whether such an \(x\) exists with welfare at least \(\Gamma\); a solution is the flow matrix \(x\). The mass flows make the population continuous. Fractional sharing remains because it is already part of the paper’s matching model.
The anchor is Theorem 5.6, proved in this paper: Max-Welfare Cardinally Stable Fractional Matching is NP-complete even when the market is bipartite and preferences are strict. In full, the decision problem takes a graph, cardinal satisfaction values, and a welfare threshold, and asks whether there is a feasible fractional matching with welfare at least that threshold and no pair whose two agents both prefer an integral match with each other to their current utilities. The theorem’s reduction is from Independent Set in cubic graphs.
For the unrestricted typed problem, this hardness transfers directly: give every agent in a discrete instance its own type of mass \(1/N\), scale each matching value by \(1/N\), and scale the welfare threshold by \(1/N\). Per-capita utilities and stability are preserved. The typed decision problem is therefore NP-hard; it is also in NP under binary rational input, since one can guess which endpoint satisfies each stability disjunction and verify a rational LP solution. Its expected classification is Class B, with hardness carried by the discrete problem.
There is also a useful support parameter question. With \(\tau\) supported types, choosing a satisfying endpoint for every acceptable type pair leaves a linear program. Trying all choices gives a \(2^{O(\tau^2)}\operatorname{poly}(\tau,L)\) algorithm, where \(L\) is the input bit length. So the mirror invites a sharper question: can this be made polynomial, or shown hard, when the support is small? The paper’s reduction uses a growing collection of distinct agents and does not establish hardness at bounded or moderate \(\tau\).
I think the authors would recognize the proposed question: it preserves their welfare objective, pairwise cardinal stability, and unit capacity, while replacing individually listed agents with cohorts that are indistinguishable on every relevant feature. The soft spot is that the theorem supports the unrestricted typed problem, not the high multiplicity regime that motivates the mirror; the reduction does not show that the problem remains hard after genuine support compression. This case covers Theorem 5.6 only. The paper’s fractional matching outcomes are not themselves the continuization claim here—the input society is now a distribution over types.
Theorem 5.6 is a genuine computational anchor, so the negative case cannot dismiss this paper as having nothing to mirror. The problem is what that theorem establishes about a *compressed population*. Giving every person their own type of mass \(1/N\) preserves the result, but leaves the support size \(\tau=N\): that is the theorem’s instance written with masses, not a high-multiplicity regime.
Real compression requires agents in a type to have identical satisfaction values toward every individual on the other side. The resulting graph has repeated, interchangeable neighborhoods; moreover, copies of a partner type are tied from each agent’s perspective. Thus the strict-preference setting of Theorem 5.6 and its gadgets do not carry over unchanged. This is not an objection that the continuous answer might be the same. It means the theorem itself supplies little evidence that population continuity creates a new algorithmic landscape.
The proposed mass-flow model is coherent for an anonymous job-sharing market, but its equal-mix condition is substantive. The paper’s matching variables let agents with identical preferences receive different mixes and therefore have different utilities. Cardinal stability checks those individual utilities against each particular partner. A type-level flow retains only a common per-capita utility. The paper gives no general reason that an individually stable matching can be symmetrized this way: stability is a disjunction, and averaging solutions can break it. The equal-mix model is a plausible symmetric-market variant, but it is not automatically the paper’s full high-multiplicity problem. A more faithful aggregation may need to track the distribution of assignments and utilities within each type, which the proposed support parameter does not capture.
Even for the symmetric variant, the stability conditions remain binary disjunctions, one per acceptable type pair. Choosing which endpoint satisfies each condition leaves an LP, so enumerating the choices gives a direct \(2^{O(\tau^2)}\operatorname{poly}(\tau,L)\) algorithm. That makes the proposed small-support question fixed-parameter tractable by immediate enumeration. With unrestricted support, assigning one type per person simply restores the original NP-hardness. The interesting middle case would need a more precise regime than “moderate support” to show a distinct algorithmic contribution.
This is the strongest negative case I can make, but it does not establish that no worthwhile mirror exists. A tied, anonymous continuum of job-sharing participants is plausible, and the mass-flow model gives it a clear formulation. I would argue that Theorem 5.6 does not yet justify the proposed mirror’s claimed value; I would not claim the mirror is incoherent or rule out a stronger one.
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.