| paper | d4-conf-atal-2018-0025 |
| 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{-complete}\), even with equal dyadic masses, \(p\equiv 0\), and only length-\(2\) patterns. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.1
statement extracted from the paper’s text layer
Given a finite type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), an acceptable-trade relation \(E\), and Model B pay and gain values \(p\) and \(g\), decide whether nonnegative masses \(x_Q\) on directed cycle patterns \(Q\) of length \(2\) or \(3\) satisfy \(\sum_Q \operatorname{occ}_t(Q)x_Q=\mu_t\) for every \(t\in T\), while admitting no blocking cycle. A blocking cycle uses arcs in \(E\) and distinct agents drawn from positive-mass status cohorts \((t_i,b_i)\), with \(g(t_{i-1},t_i)-p(t_i,t_{i+1})>b_i\) at every position, with indices taken cyclically.
A nonatomic population with mass \(\mu_t\) for each complete trade-profile type \(t\). Decision variables \(x_Q\) allocate mass to short cycle patterns, and each assigned position induces a balance-status cohort. The objective is feasibility: cover all type mass and rule out any cycle whose participants all strictly improve on their current balances.
The mass-cohort stability model may fit Biró and Fleiner’s fractional stability framework, but the mapping is not established; this could affect available methods, though it does not make the mirror unrecognizable.
fatal: False
The mirror covers Theorem 4.1’s full-coverage existence question. It leaves the verification result in Theorem 3.1, the W[1]-hardness result in Theorem 4.2, and the FPT result in Theorem 5.1 without continuous analogues.
My lead is Stable Full-Coverage Barter\(_{\infty,3}\), a continuous-population version of the paper’s full-participation question.
The anchor is Theorem 4.1, proved here by a reduction from 3-Dimensional Matching. It says that, given an instance \((G,w,\ell)\) of Stable Barter, it is NP-hard to decide whether there is a stable transaction involving all agents, even when \(\ell=3\) and \(\Delta(G)=6\). This is a hardness result about finding a stable transaction that covers everyone, not just about the existence of some stable transaction.
A plausible high-multiplicity setting is a large home-exchange network with standardized property and preference profiles. A type records the home category a family offers, which incoming categories it accepts, and how it values each category it could receive and each kind of family it might trade with. The type is complete for the market: families of the same type are indistinguishable in every respect relevant to a trade. One might imagine many thousands of families but only tens or hundreds of such profiles. This is a constructed regime, but it builds on the paper’s own vacation-rental example and its valuations of property attributes.
Formally, an instance consists of a finite type support \(T\), binary-rational masses \(\mu_t>0\) summing to \(1\), and a directed relation \(E\) of acceptable trades between types. For each acceptable trade \(t\to u\), let \(p(t,u)\) be the offering type’s pay-value and \(g(t,u)\) the receiving type’s gain-value, as in the paper’s Model B. The length bound is \(3\). A cycle pattern \(Q=(t_1,\ldots,t_r)\), \(r\in\{2,3\}\), uses acceptable arcs between consecutive types; repeated type labels are allowed, but represent distinct families. Let \(x_Q\ge 0\) be the mass of families assigned to cycles of pattern \(Q\). Full coverage requires
\[
\sum_Q \operatorname{occ}_t(Q)x_Q=\mu_t
\quad\text{for every }t\in T,
\]
where \(\operatorname{occ}_t(Q)\) counts the positions of type \(t\) in \(Q\).
The balance of a family in position \(i\) of \(Q\) is \(g(t_{i-1},t_i)-p(t_i,t_{i+1})\), with indices taken cyclically. Families of one type may receive different balances in different cycles, so the allocation induces status cohorts \((t,b)\), each with a mass \(\nu_{t,b}\). Call an allocation stable if there is no acceptable cycle pattern of length at most \(3\) and choice of current status \(b_i\) at each position such that every cohort \((t_i,b_i)\) has positive mass and every position strictly improves: \(g(t_{i-1},t_i)-p(t_i,t_{i+1})>b_i\). Positive mass in each cohort supplies a positive amount for a block; if a cohort appears more than once, that amount can simply be chosen small enough. The question is whether a stable full-coverage allocation exists; a yes-solution is a rational list of cycle masses \(x_Q\). Each family still gives and receives a whole home through a short cycle. Only the population’s allocation across cycle patterns is fractional.
I expect this mirror initially to fall on the tractable side. The 3-Dimensional Matching reduction relies on discrete choices among individual agents; splitting homogeneous type mass across cycle patterns may relax that integrality, as it does for ordinary fractional cycle-cover constraints. But coverage alone is not the problem: stability depends on which type-and-balance cohorts have positive mass. A prover would need to handle those support conditions, perhaps with a structural characterization and a continuous-optimization formulation. Further questions are whether existence is polynomial in \(\tau\) and the input bit length \(L\), whether a blocker-separation procedure is efficient, and whether the support conditions instead produce continuum-specific hardness. A high-multiplicity discrete dictionary would also need to explain when rational stable mass allocations can be rounded while preserving stability.
I think the authors would recognize this as their barter problem: it keeps their asymmetric trade values, short all-or-nothing cycles, balance comparison, and blocking notion, while changing the society from named families to mass over complete types. The mirror covers Theorem 4.1 alone; it does not claim a continuous version of the paper’s W[1]-hardness or FPT results.
The weakest point is the regime itself. If homes and preferences are too idiosyncratic, the number of complete types may approach the number of families. Also, the hardness gadgets use a sparse graph on named agents; grouping agents by type can change that structure, and fractional allocation may destroy the reduction. Tracking separate balance cohorts avoids the tempting but incorrect shortcut of giving each type a single average payoff, but it also makes the continuous stability condition harder to analyze.
I can make a case against this anchor, but I can’t make it decisive. Theorem 4.1 is a genuine computational result, and the proposed mirror is more carefully specified than a literal fractionalization: type-to-type valuations preserve the paper’s relational payoffs, and balance cohorts preserve the fact that members of one type can have different current statuses. A positive-mass cohort can supply an arbitrarily small blocking cycle. Those are sound choices, not flaws I can use to dismiss the model.
The best objection is that the high-multiplicity setting rests on a demanding market assumption: trade compatibility and both sides’ valuations must be determined by a small set of type categories. That is credible for a standardized exchange network, but much less so for the paper’s motivating cases. Kidney compatibility and home suitability can depend on individual medical or property details; encoding those details may make the type support nearly as large as the population. The proponent’s standardized-home scenario answers this objection in principle, though: it is plausible enough that I can’t claim there is no sensible regime.
The mirror also carries a substantial modeling burden. Because the blocking condition compares each participant with their current balance, it must track the masses of type-and-balance cohorts. Stability then becomes a support condition over those cohorts, alongside the full-coverage constraints. That makes the continuous problem a less direct fit for the LP and column-generation machinery that motivates the programme. But this is a reason the problem may be harder to formulate and solve, not a reason it is unworthy.
There is adjacent work on fractional stability for capacity-constrained joint activities: Biró and Fleiner show that stable allocations in finitely generated capacitated NTU games can be found using Scarf’s algorithm, including models with differing participant contributions. That makes it important to check whether the cycle-and-balance model reduces to an existing framework. It is not, on the evidence here, an exact collision: the proposed mirror’s status cohorts and full-coverage condition still need to be matched to that framework’s stability notion. [Biró and Fleiner, “Fractional solutions for capacitated NTU-games, with applications to stable matchings”](https://doi.org/10.1016/j.disopt.2015.02.002)
So the strongest honest case against is one of priority, not validity: the mirror is a specialized fractional-core problem whose plausible applications depend on unusually clean type-level interactions, and whose relation to existing fractional-stability methods needs careful checking. That case does not defeat the anchor. The negative position is weak here; the proposed mirror appears well-posed and worth considering.
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.