| paper | d4-conf-aaai-2014-0002 |
| 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}\); the rational welfare-threshold decision problem is \(\mathrm{NP}\text{-complete}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), reciprocal compatibility between types, strict rankings \(\succ_t\) over compatible partner types, and rational arc weights \(w_{tu}\) consistent with those rankings, choose pair masses \(x_{\{t,u\}}\ge 0\). Let \(d_{tu}=x_{\{t,u\}}\) for \(t\ne u\) and \(d_{tt}=2x_{\{t,t\}}\), and require \(\sum_{u\in T}d_{tu}\le \mu_t\) for every type. Maximize \(\sum_{t<u}(w_{tu}+w_{ut})x_{\{t,u\}}+\sum_{t\in T}2w_{tt}x_{\{t,t\}}\), subject to internal stability: for each compatible pair \(t,u\), define \(A_{t,u}=\sum_{v:\,u\succ_t v}d_{tv}\); require that \(A_{t,u}\) and \(A_{u,t}\) are not both positive. What is the computational complexity of finding a maximum-welfare mass matching satisfying these conditions?
A large exchange pool described by complete partner-profile types, each with mass \(\mu_t\), uniform compatibility, rankings, and arc weights. Variables \(x_{\{t,u\}}\) give aggregate pair mass and maximize total arc weight; each individual still receives an ordinary pairwise exchange, while stability rules out type pairs with positive mass on both sides currently assigned to less-preferred partners.
In kidney exchange, compatibility and value can depend on particular patient–donor pairs, so exact groups with uniform relations to every partner type may be uncommon; the proponent's plausible structured-market example does not establish how often that regime occurs.
fatal: False
The mirror covers Theorem 4 only. It leaves the paper's welfare bounds, other exchange settings, and experiments outside the proposed question.
The strongest mirror is the paper’s weighted pairwise matching problem in a large exchange pool where many agents share the same complete exchange profile. Think of patient–donor pairs in a regional or national kidney exchange: a type records the compatibility classes an agent can exchange with, their strict ranking over those classes, and the arc weights that determine welfare. A type is complete in the paper’s sense: its members agree on every preference, compatibility, and weight the model uses. A pool might have thousands of agents but only dozens or hundreds of such profiles. Each person still receives an ordinary, indivisible two-way exchange; the fractional quantities below describe how much population is assigned to each kind of exchange.
The anchor is Theorem 4: in weighted graphs, computing a maximum internally stable pairwise matching is NP-hard. The paper states this as a theorem and says its proof, deferred to the full version, is based on the hardness result for the egalitarian stable roommate problem by Feder (1992). The underlying question is whether one can maximize the total arc weight of a pairwise matching subject to internal stability: no currently matched agents can form a new pair that makes both strictly better off.
A continuous version, Weighted Pairwise Internal-Stability Mass Matching, is:
\[ \sum_{u\ne t}x_{\{t,u\}}+2x_{\{t,t\}}\le \mu_t. \]
\[
\sum_{\{t,u\}:t\ne u}(w_{tu}+w_{ut})x_{\{t,u\}}
+\sum_t 2w_{tt}x_{\{t,t\}}.
\]
A solution is the mass vector \(x\).
\[
A_{t,u}(x)=\sum_{v:\,u\succ_t v}d_{tv}.
\]
This is the mass of type \(t\) currently matched to partners it ranks below \(u\). Stability requires that \(A_{t,u}(x)\) and \(A_{u,t}(x)\) are not both positive. If they were, a positive amount of each type could leave its current assignment and pair up, with both sides improving. The condition also covers \(t=u\): positive mass of type \(t\) matched below \(t\) could be paired among itself.
This is the same welfare-and-blocking question as Theorem 4, with population mass replacing individual counts. The pair assignments remain integral for each person; splitting a type’s mass across partner types is the aggregate description that comes with a continuum population. That is an in-scope co-modification of the population model.
I would expect this mirror to be tractable when parameterized by the number of types \(\tau=|T|\), even though the paper’s unrestricted problem is NP-hard. There are at most \(O(\tau^2)\) pair variables. Internal stability depends on which pair variables are positive: for any fixed support, one can check from the rankings whether that support permits a blocking pair, then optimize over the remaining variables with a linear program. Enumerating supports gives an exact \(2^{O(\tau^2)}\operatorname{poly}(L,\tau)\) algorithm, where \(L\) is the input bit length. This is an FPT result in \(\tau\), not a claim of polynomial time when \(\tau\) is unrestricted. The mirror’s further questions include whether natural structure among compatibility classes or rankings yields a better dependence on \(\tau\), and how the continuous optimum relates to finite pools with integer counts and discrete stability.
The weak point is that the paper’s weighted graphs allow extensive agent-specific structure. In a real pool, preferences and compatibility may be individualized enough that nearly every agent has a distinct complete profile, making \(\tau\) close to the population size and eliminating the parameterized advantage. Also, the paper’s NP-hardness result does not itself establish hardness for a low-\(\tau\) regime; fractional mass allocation may remove the combinatorics behind its reduction. The case for the mirror rests on the large-pool regime where repeated, genuinely exchange-equivalent profiles are plausible—not on a claim that every kidney exchange instance has few types.
This case covers Theorem 4 only. It does not claim to mirror the paper’s welfare bounds, its limited-length exchange hardness results, or its experiments.
The strongest objection is that the proposed mirror needs a much more structured exchange graph than Theorem 4 assumes. To aggregate agents exactly, a type must preserve every relevant compatibility, ranking, and weight relationship—including how other agents rank its members. In a kidney exchange pool, crossmatches and pair values can depend on the specific patient–donor pairs. Grouping by broad medical categories can therefore lose information that determines both welfare and blocking. Two pools with the same category masses and aggregate edge statistics can have different reciprocal blocking pairs.
Exact types avoid that loss only when agents are interchangeable across the whole weighted graph: their relationships to every other type must be uniform. That is a demanding condition in the paper’s motivating domain, and the paper does not establish that its experimental instances have large groups of such agents. This makes the mirror a structured-graph variant, not an automatic high-multiplicity version of the weighted problem in Theorem 4.
That objection weakens against the best alternative, though. A market where compatibility and value genuinely depend on a small set of partner types is a sensible exchange model, and it can contain large populations of interchangeable agents. The proposed mass formulation then captures the welfare and internal-blocking question faithfully, with indivisible exchanges for individuals and fractional assignments at the population level. The paper contains no continuous treatment of that computational problem.
So the negative case is a warning about how narrow the plausible type structure may be, especially for kidney exchange. It does not defeat the type-based market model, and I cannot honestly support the universal claim that no worthwhile scenario exists. Under the programme’s stated standard, Theorem 4 remains a viable anchor.
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.