| paper | d4-conf-ijcai-2021-0026 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; a qualifying rational allocation always exists. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a rational mass distribution μ over a finite set of complete compatibility types, a compatibility graph on those types, and a partition into fairness groups, find a maximum-matched-mass allocation that satisfies individual rationality and attains the greatest minimum Max-M-Min selection ratio over all capacity-feasible allocations, or report that none exists. Define each group’s lower bound as the greatest mass it can match using only within-group exchanges, and its upper bound as the greatest mass it receives among maximum-mass allocations; use the paper’s convention when the bounds coincide.
Types \(t ∈ T\) carry masses \(μ_t\) and group labels. For each compatible unordered pair of types, including a type paired with itself when such exchanges are possible, let \(x_{tu} ≥ 0\) be the mass of pairs formed. Enforce \(∑_{u ≠ t} x_{tu} + 2x_{tt} ≤ μ_t\); group matched mass \(z_i\) counts the mass used at its endpoints. Maximize total matched mass subject to individual rationality \(z_i ≥ ℓ_i\), and require the allocation to attain the maximum over capacity-feasible allocations of μin_i (z_i-ℓ_i)/(u_i-ℓ_i), with the paper’s convention for zero denominators.
The case gives no empirical evidence that complete compatibility types remain few in a real registry; if nearly every pair has a distinct profile, the mirror offers little compression.
fatal: False
The mirror covers Theorem 4 for the Max-M-Min quota choice. It leaves the paper’s other quota choices, graph-specific running-time bounds, and exchange settings beyond pairwise matching aside.
I think the pairwise exchange and group-fairness problem has a credible continuous mirror in a large exchange registry whose participants fall into a much smaller number of recurring compatibility types. The strongest anchor is Theorem 4, proved in this paper: given a compatibility graph and a choice of upper and lower quotas from Table 1, Algorithm 2 finds a matching that is maximum, individually rational, and fair whenever such a matching exists, in polynomial time. Theorem 2 helps select the right case: for groups with different neighbors, Max-M-Min is the quota choice the paper identifies as compatible with all three properties.
Here is the mirror I would put to a prover. The society is an atomless population of mass \(1\), described by rational masses \(\mu_t\) over a finite support \(T\), with \(\sum_t\mu_t=1\). A type \(t\) is a patient-donor class whose members have the same compatibility relationships in the model, and carries a group label such as hospital or region. The compatibility graph \(E\) connects types that can exchange with each other. The regime is a large national or cross-regional pool with many patient-donor pairs but relatively few recurring clinical and logistical profiles: \(n\) is much larger than the number \(\tau=|T|\) of types. The paper’s examples of grouping pairs by compatibility attributes or geography make this a natural instance regime.
For every compatible edge \(e=\{t,u\}\), let \(x_e\geq 0\) be the mass of pairs formed between those types. Each type’s capacity is respected:
\[ \sum_{e\ni t} x_e \leq \mu_t \qquad (t\in T). \]
Let \(z_i(x)\) be the mass of matched patient-donor pairs in group \(G_i\): an edge contributes one unit at each endpoint, so an edge within a group contributes twice its mass. The objective is to maximize \(\sum_i z_i(x)\), the total matched population. For individual rationality, define \(\ell_i\) as the greatest mass group \(G_i\) could match using only exchanges within that group. Define \(u_i\) as the greatest mass from \(G_i\) among globally maximum mass matchings. The Max-M-Min selection ratio is
\[ \rho_i(x)=\frac{z_i(x)-\ell_i}{u_i-\ell_i}, \]
using the paper’s convention when \(u_i=\ell_i\).
The continuous problem: given the rational type masses, compatibility graph, group partition, and Max-M-Min rule, find a mass allocation \(x\) that maximizes total matched mass, satisfies \(z_i(x)\geq \ell_i\) for every group, and attains the greatest possible value of \(\min_i\rho_i(x)\) over all capacity-feasible allocations. Return such an \(x\), or report that none exists. The allocation is meaningful as a continuum matching: each type’s mass can be split among compatible types, and equal masses on an edge can be paired. Each individual is still either matched once or unmatched; it is the amount of a type assigned to each option that is fractional.
I expect this mirror to be tractable. With finite type support, the mass constraints and matched-mass totals are linear. The maximum, each \(\ell_i\), and each \(u_i\) can be obtained by linear programs; the max-min fairness step is another linear program once those quota values are known. The result is a concrete Class A question, with size governed by \(\tau\), the number of compatibility edges, and the rational input bit length. It preserves the paper’s pairwise compatibility constraints and its three criteria; it changes the unit from a named patient-donor pair to a mass of interchangeable pairs.
The continuous problem covers the paper’s joint maximum-matching, individual-rationality, and group-fairness result. It does not claim to mirror every organ-exchange problem, such as online arrival or longer exchange cycles. The paper’s earlier observation that checking core existence is co-NP-hard concerns a different question and is not a numbered computational result here, so I would not use it as an anchor.
My weakest point is the type-count assumption. If every patient-donor pair has a unique modeled compatibility profile, then \(\tau\) may be close to \(n\), and the population description offers little compression. The case rests on a real registry regime with repeated complete types, not on kidney exchange as a whole. Also, this is an algorithmic anchor: it does not show that hardness dissolves, because the paper’s main anchored result is already polynomial-time. The useful follow-up questions are whether the continuous solution admits a controlled rounding to large finite registries, how the fairness guarantees behave under rounding, and whether the paper’s universal existence result for Max-M-Min carries over to the atomless model.
Theorem 4 is a real computational anchor: it asks for a maximum, individually rational, fair matching and gives a polynomial algorithm. The strongest case against a mirror is about its payoff, not whether the question can be formulated.
For groups whose members have identical neighbors, the paper already compresses the graph to one node per group with an integer capacity. If the continuous model uses those same compatibility classes, its natural formulation has one variable \(x_e\) per compatible pair of types and constraints \(\sum_{e\ni t}x_e\leq\mu_t\). Group matched masses, self-matching bounds, and the Max-M-Min objective can all be expressed with linear programs over that compact graph. This is a clean mirror, but it adds no new computational machinery: the paper already gives polynomial algorithms in the number of groups for the corresponding quota problems. The continuous version is a fractional capacity variant of a problem already tractable in its high-multiplicity representation, with no difficult pricing problem or new complexity boundary to chart.
The more ambitious version keeps geography as the fairness grouping and refines each region into complete compatibility types. That preserves the meaning of the matching constraints, but its support size depends on how many distinct clinical profiles the registry contains. If tissue and other patient-donor attributes produce nearly unique compatibility profiles, the type support can approach the number of pairs and the model offers little compression. Coarsening those profiles to keep the support small risks asserting compatibility between pairs that are not actually interchangeable. This makes the continuous formulation’s practical value depend on an empirical feature of a registry, rather than following from the paper’s general different-neighbor model.
Still, that does not defeat the mirror in every scenario. A large registry with many repeated, operationally meaningful compatibility profiles is plausible, and mass matching among those profiles is coherent. The paper itself motivates groups by compatibility types, so I cannot honestly claim that no worthwhile continuous mirror exists. My negative case is narrower: Theorem 4’s mirror looks low priority for ChoCo because the best exact-type version largely inherits the paper’s existing compact algorithm, while the more realistic geographic version may lose its compression when types are made complete.
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.