| paper | d4-conf-atal-2013-0076 |
| 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: \(\mathrm{NP}\text{-hard}\), even for an empty initial matching and uniform positive dyadic type masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Given finite male and female type sets \(T_M,T_W\), rational type masses with each side totaling \(1\), complete externality valuation vectors \(\pi_t(a,b)\), and a feasible mass matching \(x\), decide whether there are coalition masses \(q_t\leq\mu_t\), with some \(q_t>0\), and a feasible reassignment \(x'\) that blocks \(x\). Split each type's mass into coalition and outsider submasses; preserve all outsider-to-outsider matches, allow new matches only within the coalition, and require every participating unit to form or sever a match. For each participating type \(t\), compare \(U_t(x)=\sum_{a,b}x_{ab}\pi_t(a,b)\) with \(U_t(x')=\sum_{a,b}x'_{ab}\pi_t(a,b)\); every participating type must weakly gain and at least one type with \(q_t>0\) must strictly gain.
A nonatomic one-to-one matching market with finitely many complete externality types, rational masses, and a mass-flow assignment \(x_{ab}\). The question is feasibility of a neutral blocking reassignment; there is no optimization objective.
Finite core blockers may involve only \(O(1)\) agents, whose mass vanishes as the market grows, so the atomless core can have different stable outcomes and Theorem 9's hardness has no automatic transfer.
fatal: False
The mirror covers Theorem 9's neutral one-to-one stable-set membership result; it leaves the non-emptiness results, other attitudes, many-to-many matchings, and pairwise-stability results aside.
My lead is the one-to-one neutral stability result. Theorem 9, proved in this paper using the reduction from Theorem 2, says: given a one-to-one matching game with additive externalities and a proposed matching, deciding whether that matching belongs to the neutral stable set is coNP-complete. The decision is whether there is *no* coalition that can rearrange matches among its members and cut matches with outsiders so that every member weakly gains and at least one strictly gains. Under neutrality, outsiders keep their existing matches and form no new ones. In the paper’s one-to-one setting, setwise stability coincides with the core.
Here is the continuous mirror I would ask the authors to study: Atomless Neutral Core Membership for One-to-One Matchings with Additive Externalities.
An instance has finite male and female type sets \(T_M,T_W\). A type specifies an agent’s side and their complete additive-externality valuation vector: \(\pi_t(a,b)\) is the value to type \(t\) of a match between types \(a\in T_M\) and \(b\in T_W\). Each type has rational mass \(\mu_t\), with the male masses and female masses each summing to \(1\). The proposed outcome is a mass matching \(x_{ab}\geq 0\), where each unit of mass receives at most one match:
\[ \sum_b x_{ab}\leq \mu_a,\qquad \sum_a x_{ab}\leq \mu_b. \]
A type-\(t\) agent’s normalized utility is \(U_t(x)=\sum_{a,b}x_{ab}\pi_t(a,b)\). The question is whether \(x\) is stable against every measurable coalition of submasses: can some coalition change matches involving its members, form new matches only within the coalition, and leave all matches between outsiders intact, while weakly improving every participating type’s utility and strictly improving at least one type of positive coalition mass? As in the paper, every member of the coalition must take part in an action. A “no” answer has a witness consisting of the coalition masses and a feasible reassignment; a “yes” answer says no such blocking deviation exists.
A plausible regime is a large annual matching market with many workers and positions but few repeated profiles: for example, workers grouped by a small number of qualification classes and positions by a small number of employer classes. Agents in a type share the same externality values, including how they value matches elsewhere in the market. The number of agents can be large while the number of types \(\tau\) stays small. The mass matching is an aggregate description: each person still gets at most one integral match. This continues the population, with fractional edge masses recording aggregate assignments. It does not make the outcomes themselves divisible.
I expect this membership problem to become tractable when \(\tau\) is fixed, perhaps through a finite optimization formulation over possible coalition type supports. That is a conjecture for the mirror, not a result of the paper. The source theorem’s Knapsack reduction uses item-specific weights, so it does not establish hardness when many agents share a small number of complete types. A natural next question is whether the continuous problem admits an algorithm polynomial in \(\tau\) and the input bit length, or whether type diversity itself yields hardness. A second question is how the continuous and discrete membership problems relate when a discrete market has rational type proportions.
The mirror is especially plausible because the paper already has type-level utilities: agents with the same complete valuation vector receive the same utility from a given matching. The main co-modification is to describe one-to-one assignments by mass flows and allow coalitions to select submasses. The weakest point is that a blocking coalition is a strong part of the original question, and its exact atomless interpretation must preserve the paper’s rule that every deviator acts. Also, the theorem’s hardness proof does not show that hardness survives in a low-\(\tau\) regime. Those limitations make tractability a serious possibility, but they do not remove the core question the theorem asks: whether a proposed matching is immune to profitable neutral deviations.
Theorem 9 is a real computational result: neutral stable-set membership for one-to-one matchings with additive externalities is coNP-complete. So the decisive objection that there is no result to mirror does not apply.
The strongest case against is that a useful high-multiplicity regime may be hard to motivate for this particular model. A type must include an agent’s entire valuation vector over possible matches, including externalities from other people’s matches. Two firms with similar hiring policies still count as different types if they value even one possible match differently. The paper’s general model permits those values to depend on named agents, and its examples emphasize competitive effects between firms. In such settings, exact type counts may grow with the number of agents. Coarsening types to recover a small support could discard the very externality information that determines whether a coalition blocks.
Theorem 9’s Knapsack reduction reinforces that concern: its item-specific weights and values are encoded in agents’ valuations. In a mass model, those agents can be represented as distinct types, but then the support grows with the reduction. If instead they are made interchangeable and divisible, the reduction’s discrete item choices no longer transfer directly. That does not defeat the continuous question; it does mean the theorem itself offers little reason to expect the hard part to survive in a genuinely low-type regime.
There is also a modeling choice to settle. The paper sums an agent’s value over all matches, whereas the proposed mirror uses a population-normalized aggregate. That normalization is natural for a population model, but the resulting atomless core tests deviations by positive masses; it need not preserve every finite-market blocking coalition exactly. A stronger mirror could track matched subpopulations and retain each agent’s type-specific payoff, but it would still need a convincing setting where agents share their *complete* externality vectors.
That is the best negative case I can make: the plausible low-support regime may be narrower than the proposal suggests, and the source hardness is tied to item-level distinctions that mass divisibility can erase. It does not establish that no worthwhile mirror exists. A market with repeated worker and employer classes and class-level externalities is still plausible, and asking whether continuous neutral-core membership becomes tractable there is well-posed. On the supplied rubric, I cannot honestly say this anchor is defeated.
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.