| paper | d4-conf-ijcai-2017-0719 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Polynomial-time solvable in \(m,\tau,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given finitely many club types \(T\) with rational masses \(\mu_t\ge0\), \(\sum_t\mu_t=1\), finite donor and patient slots per type, parameters \(\alpha_t\ge1,\gamma_t\ge0\), and rational compatibility and weights for allowed donor-slot/patient-slot type pairs, does there exist a measurable allocation of trades in an atomless population of clubs with total weight at least \(B\), where each slot is used at most once and almost every type-\(t\) club has integral external-trade counts \(d_c,p_c\) satisfying \(d_c\le\alpha_t p_c+\gamma_t\)?
Use a configuration LP with a variable \(\lambda_{tq}\ge0\) for each integral local trade pattern \(q\) of type \(t\), require \(\sum_q\lambda_{tq}=\mu_t\), and balance mass on every allowed directed slot-pair trade. Maximize \(\sum_{t,q}\lambda_{tq}w(q)\); pricing appears polynomial by enumerating feasible count pairs \((d,p)\) and optimizing the slot choices.
This mirrors only the uncapped generalized clearing problem in Theorem 1; it leaves operation-frame scheduling, its formulation, and the experimental welfare comparisons untouched.
The strongest honest case is a mirror of Theorem 1, which states that the decision version of uncapped generalized clearing is NP-complete. The paper presents this as a result proved there, not as a result cited from elsewhere. Its underlying problem is: given disjoint clubs \(c=(D_c,P_c,\alpha_c,\gamma_c)\), compatible donor–patient edges with weights, and the rule that each donor and patient is used at most once, choose trades of maximum total weight while every club satisfies
\[
\text{outgoing trades from }c \leq \alpha_c(\text{incoming trades to }c)+\gamma_c.
\]
The decision question is whether a feasible set of trades reaches a specified value.
The paper’s proof reduces Set Packing. For each item \(u_i\), it creates a one-donor club \(a_i\) with \(\gamma_{a_i}=1\). For each set \(S_j\), it creates a one-patient club \(c_j\), plus a club \(b_j\) with one donor and \(|S_j|\) patients. The item donor for \(u_i\) can donate to the corresponding patient in \(b_j\) when \(u_i\in S_j\), for weight \(1\); the donor in \(b_j\) can donate to \(c_j\), for weight \(M=|\mathcal U|+1\). The intended construction sets \(\alpha_{b_j}=1/|S_j|\), so taking the high-weight edge requires filling all of \(b_j\)’s patients. Then a solution of weight in \([kM,(k+1)M)\) corresponds to \(k\) disjoint sets. Membership in NP follows by checking a proposed set of trades.
There is a significant caveat to that anchor: Definition 1 requires \(\alpha_c\geq 1\), while this reduction uses \(\alpha_{b_j}=1/|S_j|\), which is less than \(1\) whenever \(|S_j|>1\). As printed, that proof sketch does not establish the theorem under the stated parameter restriction. The theorem is still the paper’s named hardness claim, but I would not present its proof as sound without resolving that mismatch.
A plausible high-multiplicity regime is a large centralized exchange with many clubs drawn from a moderate number of recurring clinical and policy profiles. A type would specify the club’s donor and patient slots, their clinical compatibility classes, \(\alpha\), initial debt \(\gamma\), and the weight of each possible slot-to-slot trade. Mass \(\mu_t\) is the fraction of clubs of type \(t\), with \(N\gg\tau\), where \(N\) is the number of clubs and \(\tau\) the number of types. This fits the paper’s club-based model: it keeps the same agents, trades, weights, and participation rule, while making the population of clubs the continuous object.
My proposed mirror is Continuous Generalized Club Clearing. Its input is a finite set of types \(T\), rational masses \(\mu_t\) summing to \(1\), each type’s finite donor and patient slots, its rational \(\alpha_t,\gamma_t\), and the compatible slot pairs and their rational weights. Imagine an atomless population of clubs of each type, with mass \(\mu_t\). A solution is a measurable matching of compatible donor slots to patient slots on other clubs. Each slot is used at most once. For almost every individual club, its selected trades remain integral and satisfy the paper’s own condition
\[
d_c \leq \alpha_t p_c+\gamma_t,
\]
where \(d_c\) and \(p_c\) are that club’s outgoing and incoming trade counts. The question is whether an allocation of value at least \(B\) exists; equivalently, maximize the total weight per unit mass of clubs. Fractional quantities arise across a type’s population, not as fractional kidneys or fractional actions for a club.
I expect this mirror to be Class A, tractable by a configuration LP. For each type \(t\), let \(Q_t\) be its finite set of integral local trade patterns, each respecting the club’s slots and balance rule. Let \(\lambda_{tq}\) be the mass of type-\(t\) clubs assigned pattern \(q\). Require \(\sum_{q\in Q_t}\lambda_{tq}=\mu_t\), and balance the mass of each type-to-type slot trade selected by source patterns with the mass selected by destination patterns. Maximize the mass-weighted trade value.
There may be exponentially many patterns, but the pricing step for a type appears polynomial: each donor slot chooses an unused option or its best compatible destination, and each patient slot chooses an unused option or its best compatible source. The only coupling between those choices is the single count inequality \(d_c\leq\alpha_t p_c+\gamma_t\). Enumerating the possible numbers of selected donor and patient slots and taking the best choices for each count pair gives polynomial-time pricing in the slot and compatibility descriptions. That gives a concrete route to solving the continuous problem through the LP’s dual, with running time measured in \(\tau\), the number of slots and compatibility classes, and the input bit length \(L\).
This is recognizably the authors’ clearing problem: it retains exchange clubs, matching, weights, and the exact per-club participation constraint. It does not replace their question with outcome lotteries or continuous time. It covers Theorem 1’s uncapped clearing problem only; the operation-frame scheduling model and the experiments are outside this mirror.
The mirror also clarifies where the discrete hardness might go. The Set Packing reduction relies on choosing indivisible clubs corresponding to individual sets. In a continuum, mass of a type can be divided among different integral local patterns, so the set-selection integrality can disappear into the configuration LP. Whether the discrete problem admits useful additive rounding from this LP, and how the answer depends on \(N\), \(\tau\), and club size, are natural follow-up questions. The reduction as printed uses distinct set-incidence patterns, so it does not itself demonstrate hardness in a regime with many repeated types.
The weakest point is the regime’s plausibility for real exchanges. Clinical compatibility and patient-specific priorities can make clubs’ profiles nearly unique; if the type must encode every such distinction, \(\tau\) may approach \(N\), leaving little high-multiplicity structure. And the paper’s sole named hardness anchor has the parameter mismatch above. Those are real limitations, but they do not make the continuous question artificial: it is a precise population version of the paper’s own uncapped clearing model, and its tractability boundary is worth establishing.
The strongest case against this mirror is that the configuration LP may model a much narrower market than the paper’s clearing problem. It requires a finite set of club types such that compatibility and edge weights are determined by the two endpoint types. The paper’s input is an arbitrary compatibility graph, and its UNOS data include pair-specific clinical and logistical details. If those details make most clubs’ compatibility profiles unique, then a type must encode nearly the whole graph and \(\tau\) approaches the number of clubs. If types are coarsened, the model replaces those specific edges with a typed market in which endpoint classes can be matched according to aggregate flows. That is a clean regime, but the paper does not show that it describes its reported instances.
There is also a real defect in the anchor’s proof: the Set Packing reduction sets \(\alpha_{b_j}=1/|S_j|\), contrary to Definition 1’s requirement that \(\alpha_c\geq 1\). For \(|S_j|>1\), the displayed construction does not establish Theorem 1 as stated. This weakens the theorem’s evidentiary basis, though it does not erase the numbered complexity claim or make its decision problem uninteresting.
Those objections do not defeat the better mirror. A large exchange with repeated donor and patient profiles, type-determined compatibility, and shared club parameters is a plausible regime. In that setting, the proposed configuration LP appears to preserve the paper’s essential features: indivisible actions and balance constraints for each club, with only the population of clubs made continuous. Its pricing argument is credible under those assumptions. One could also extend the mirror to operation frames by giving types finite slot patterns over frames and scaling capacity with population.
So the honest negative case is limited: the proponent has not shown that this mirror captures the paper’s irregular real-data market, and its hardness anchor has a proof mismatch. But a recurring-profile exchange remains a sensible scenario, and its continuous clearing question is recognizable as the authors’ problem. I cannot make a convincing case that no worthwhile continuous mirror exists in any scenario.
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.