| paper | d4-conf-sagt-2019-0004 |
| 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→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\): every valid instance admits a rational weakly stable allocation. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
For each side \(t\in\{0,1,2\}\), let \(T_t\) be a finite set of types, each with a strict ranking of the types in \(T_{t+1\bmod 3}\), and let \(\mu_t(a)\in\mathbb{Q}_{>0}\) be their masses, summing to \(1\) on each side. Does there exist a rational allocation \(x_{a_0,a_1,a_2}\ge 0\) and unmatched mass \(u_t(a)\ge 0\) satisfying \(\sum_{\mathbf a:a_t=a}x_{\mathbf a}+u_t(a)=\mu_t(a)\), such that no triple \((a_0,a_1,a_2)\) has positive willing mass on all three sides? Here the willing mass of type \(a\in T_t\) for next-side type \(b\) is \(u_t(a)+\sum_{\mathbf c:c_t=a,\ b\succ_a c_{t+1}}x_{\mathbf c}\).
A finite support of role-specific preference types with rational masses; decision variables are masses \(x\) assigned to type triples and unmatched masses \(u\). Feasibility requires the type-mass marginals, and weak stability requires at least one side to have zero willing mass for every type triple; there is no welfare objective.
Theorem 5 ranks named individuals, so small-support aggregation requires replacing those rankings with rankings over partner categories; whether the authors would accept that changed preference domain as their problem remains the main risk.
fatal: False
The mirror covers Theorem 5's stable-matching existence decision in a category-based continuum. It does not establish that the paper's individual-level hardness reduction or its specific nonexistence construction survives aggregation.
My lead is a continuous mirror of Theorem 5, proved in this paper. It says that for every \(k\ge 3\), deciding whether a complete-list cyclic \(k\)-dimensional stable-matching instance has a weakly stable matching is NP-complete. Here, weak stability means there is no family in which every agent prefers the next agent in that family to their current partner. The paper proves the theorem by reducing from incomplete-list instances and establishing NP membership; the underlying NP-completeness result for \(k=3\) in Theorem 3 is cited from Biró and McDermid. I would mirror the \(k=3\) case.
Call the mirror 3-Cyclic Continuum Stable-Allocation Existence. For each side \(t\in\{0,1,2\}\), the input gives a finite set \(T_t\) of agent types and a rational mass \(\mu_t(a)>0\) for each type \(a\in T_t\), with total mass \(1\) on each side. A type is a side plus a complete strict ranking of the types on the next side, modulo \(3\). Its members are interchangeable in every respect the matching uses. The action is an allocation \(x_{a_0,a_1,a_2}\ge 0\): the mass of families made from those three types. Unmatched mass \(u_t(a)\ge 0\) is also allowed, with
\[
\sum_{\mathbf a:\,a_t=a}x_{\mathbf a}+u_t(a)=\mu_t(a).
\]
The question is whether a stable allocation exists. There is no welfare objective: the decision is whether some allocation meets the feasibility and stability conditions.
For type \(a\in T_t\) and a proposed next-side type \(b\in T_{t+1}\), let
\[
D_a(b)=u_t(a)+
\sum_{\substack{\mathbf c:\,c_t=a\\ b\succ_a c_{t+1}}}x_{\mathbf c}.
\]
This is the mass of type \(a\) currently unmatched or assigned to a type it ranks below \(b\). A triple \((a_0,a_1,a_2)\) blocks if \(D_{a_t}(a_{t+1})>0\) for all three sides, with indices modulo \(3\). Such a block can be formed by taking an equal positive mass of willing agents from each side; each person still receives one integral family bundle. A solution is a rational allocation \(x,u\) satisfying the marginal equations and having no blocking triple. This makes the question precise for a prover while allowing type-level averages to be fractional.
A plausible regime is a large, repeated three-sided network-service clearinghouse of the kind the paper names as an application. Each unit on a side represents an agent in a role; units with the same full preference ranking over next-role categories form one type. The number of agents \(N\) can be very large while the total support \(\tau=\sum_t|T_t|\) stays comparatively small. It is a sensible high-multiplicity setting if service classes, rather than personal identities, determine which partners are preferred.
My weak forecast is Class A for this high-multiplicity regime: fractional mass allocation could remove the individual combinatorial choices that drive the finite construction, and for fixed \(k=3\) the type-level family variables number only \(O(\tau^3)\). That is a research hypothesis, not an LP result. The stability condition is disjunctive—each candidate triple must have at least one side with zero willing mass—so finding an allocation is not plainly linear. A main follow-up is whether that structure admits a \(\mathrm{poly}(\tau,L)\) algorithm, or whether it makes the mirror hard in its own right.
The weakest point is the quotient from named agents to preference classes. The paper’s agents rank particular individuals, while this mirror has them rank counterpart types; strict rankings among individuals in the same class disappear. The theorem’s gadget reduction may depend on exactly those distinctions, so its hardness does not automatically transfer, and the authors might regard this as a different matching problem. I think the mirror remains recognizable because it preserves the paper’s central question—whether a weakly stable cyclic three-way allocation exists—in a plausible large-cohort market. But the author-recognition test turns on whether type-level partner categories are acceptable as the objects of preference.
This case covers Theorem 5’s complete-list existence problem in that role-based regime. It does not claim that the paper’s specific nonexistence example or its individual-level reduction survives aggregation.
Theorem 5 is a real computational anchor, so the case against it has to be about the model, not the fact that its answer might change.
The strongest objection is that the paper’s agents are distinguished by the very preferences that stability tests. With strict complete rankings over named partners, even agents with identical outgoing lists can differ in how others rank them. A type complete enough to preserve those distinctions has essentially one member: any agent on the preceding side ranks every agent on this side in a different position. Thus an identity-preserving version has support growing with the population. Giving each singleton type mass \(1/n\) records the finite instance in different units; it does not produce the small-support high-multiplicity regime ChoCo is after.
The proponent’s answer is to let agents rank *types* of partners. That is coherent, and a network-service market where participants care only about service categories is plausible. But it changes the preference domain: members of a partner type are now indistinguishable to everyone, whereas the paper assumes strict rankings of individuals. Preserving the original distinctions would require tracking rank positions within each category, which restores the growing or continuous type space; discarding them yields a category-preference matching problem. That may be a worthwhile problem in its own right, but the bridge from it to Theorem 5 is not established by population continuization alone.
Nor does the proposed \(O(\tau^3)\) allocation table itself supply the continuous-optimization rationale. Stability requires, for every type triple, that at least one of its three willing masses be zero—a disjunction of linear equalities. The resulting feasibility problem is not the natural LP relaxation suggested by the number of allocation variables. This does not make the question uninteresting, but it leaves the proposed Class A forecast without a structural basis.
So the negative case is strongest against calling this a mirror of the paper’s theorem: exact types give no useful aggregation, while category types alter what agents rank. It is not airtight against the broader claim that a category-based cyclic stable-allocation problem is worth studying. If the authors accept partner classes as a natural version of their problem, that scenario could survive the recognition test; the paper alone does not settle that point.
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.