| paper | d4-conf-atal-2016-0250 |
| 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→P discrete result → its continuous mirror
Answer: In \(\mathrm{P}\): every valid instance is a YES-instance, and the minimum removal cost is \(0\). Decision takes \(O(L)\) time including reading the input. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a finite type set \(T\), a compatibility graph \(H=(T,F)\), rational type masses \(\mu_t\) summing to \(1\), and nonnegative rational removal costs \(w_t\), choose removed masses \(r_t\in[0,\mu_t]\) to minimize \(\sum_{t\in T} w_t r_t\). For the remaining masses \(q_t=\mu_t-r_t\), the society is stable if there are nonnegative type payoffs \(p_t\) with \(p_t+p_u\ge1\) for each \(\{t,u\}\in F\), and \(\sum_t q_t p_t\) equals the maximum matching mass \(\max\sum_{\{t,u\}\in F}x_{tu}\), subject to \(\sum_{u:\{t,u\}\in F}x_{tu}\le q_t\) for each \(t\) and \(x_{tu}\ge0\). Find a minimum-cost stabilizing removal.
A nonatomic population of interchangeable roles \(t\in T\), with mass \(\mu_t\), uniform unit-deal compatibility given by \(H=(T,F)\), and per-person removal cost \(w_t\). The decision variables are removed masses \(r_t\); the objective is \(\sum_t w_t r_t\), and stability is witnessed by a maximum mass matching and its dual type payoffs. The LP dual certifies stability for every residual mass vector, so the continuous optimum is \(0\).
The mirror covers weighted vertex-removal stabilization from Theorem 8. It leaves the unweighted stabilization algorithms, edge-addition results, and weighted edge-addition hardness result untreated.
The strongest positive case is the weighted vertex-removal result, Theorem 8. It is proved in this paper: given a graph \(G=(V,E)\) and nonnegative vertex-removal costs \(w\), finding a minimum-cost set \(X\subseteq V\) such that
\[
\nu(G-X)=\nu_f(G-X)
\]
is NP-hard. Here \(\nu\) is the maximum matching size and \(\nu_f\) the fractional matching optimum. The authors prove this by reduction from a vertex-removal problem that encodes CLIQUE.
A natural high-multiplicity setting is a large exchange or labor market where participants fall into a modest number of genuinely interchangeable roles. For example, a role might specify a participant’s qualifications, location, bargaining-relevant attributes, and removal cost. Every participant of type \(t\) can make the same unit-value deal with every participant of a compatible type \(u\). The market might have millions of participants but only dozens of types. The type must include the removal price: if prices differ, those participants are different types.
Here is the continuous problem I would hand to a prover. Call it Minimum-Mass Removal for Core Stability\(_\infty\). An instance consists of a finite type set \(T\), a compatibility graph \(H=(T,F)\), rational type masses \(\mu_t\ge 0\) summing to \(1\), and nonnegative rational removal costs \(w_t\). Choose removed masses \(r_t\in[0,\mu_t]\), minimizing
\[
\sum_{t\in T} w_t r_t.
\]
The remaining society has masses \(q_t=\mu_t-r_t\). A solution must give the removals, a matching of the remaining population, and a core payoff: every agent of type \(t\) gets payoff \(p_t\ge0\); every compatible pair satisfies \(p_t+p_u\ge1\); the total payoff equals the maximum feasible matching mass.
This keeps the paper’s underlying question—how much must be removed to make the matching game have a nonempty core—while continuing the population. Each individual still makes at most one whole deal. The aggregate can divide a type’s mass among different compatible types because it represents a nonatomic cohort, not a divisible bundle assigned to one person. Coalition values are defined by the maximum mass of unit-value deals they can form from their members.
I expect this mirror to be tractable, in fact always to have optimum \(0\). For any surviving mass vector \(q\), the matching problem is a fractional matching LP: choose \(x_{tu}\ge0\) for \(\{t,u\}\in F\), with incident matched mass at most \(q_t\). Its dual chooses \(p_t\ge0\) with \(p_t+p_u\ge1\) on every compatible pair. Strong duality gives an optimal matching and optimal payoffs. Those payoffs support the grand coalition with equality and bound every subcoalition’s deal value, so the core is nonempty without removal. The LP has size polynomial in the number of types and compatibility links, with rational input of bit length \(L\).
That makes this a credible mirror of Theorem 8 precisely because it exposes what continuization changes: the discrete hardness comes from the gap between integral and fractional matching, while a nonatomic population can split into compatible cohorts and realize matching mass as whole-agent deals. The scope is deliberately narrow: it mirrors weighted vertex removal for core nonemptiness, not the paper’s edge-addition results or arbitrary individual networks.
The weak point is substantial. This market assumes compatibility is determined entirely by type, so its finite networks are complete between compatible type classes; Theorem 8’s hardness uses arbitrary individual-level structure and does not establish hardness in a regime with many agents but few types. And the continuous answer is degenerate: no removal is needed. A referee could regard that as too far from the paper’s interesting stabilization problem. I think it remains worth asking because it is the direct high-multiplicity version of the same core-stabilization objective, and discovering that the objective collapses is itself a sharp account of where this discrete hardness stops helping.
The follow-on questions are whether finite replications of such type markets need only \(o(N)\) removals as population size \(N\) grows, and which changes to the market assumptions—such as persistent individual-level compatibility differences—allow empty-core phenomena to survive the continuum limit.
Theorem 8 is the strongest anchor, and the best objection is that its continuous version loses the stabilization problem itself. A role-based market is a coherent high-multiplicity setting: participants can share types when their qualifications, compatibility, and removal costs match. So the problem is not that such a scenario is implausible.
The difficulty is what happens to matching in that model. With an atomless population, a mass of type \(t\) can be split among its compatible types. For any remaining masses \(q_t\), the achievable matching mass is therefore the fractional matching LP. Its dual assigns payoffs \(p_t\) with \(p_t+p_u\ge 1\) for each compatible pair. Strong duality gives payoffs that support the grand coalition, and those same constraints support every subcoalition. Thus the core condition holds for every residual population. The stabilization objective has no instance-dependent decision left: removal mass zero is always feasible, whatever the type masses or removal costs.
That is a continuum degeneration, rather than an objection that the continuous answer is merely easy. In the finite paper, stabilization asks whether the integer matching value equals its fractional relaxation. In the atomless model, fractional matching is the matching that the population can actually perform. The integrality defect that drives vertex removal has vanished from the object being optimized.
The more faithful alternatives run into the same boundary. If types record arbitrary individual compatibility patterns, the number of types can grow with the number of people, so the model no longer gains a high-multiplicity representation. If many people share a finite set of roles, compatibility is uniform between roles and the atomless matching LP applies. Keeping whole-person removals and exact finite matching instead preserves parity and other granularity effects, but then the model remains discrete; per-capita costs also erase fixed-size corrections as the population grows.
I would still vote against this mirror as worthwhile computational work: its most natural formulation reduces Theorem 8’s optimization to a core certificate already implicit in the paper’s LP framework. But the negative case has a real limit. The role-based model is a sensible population-continuous object, and the programme may value identifying this collapse as a boundary result. If such a boundary result counts as worthwhile, the proponent’s case survives.
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.