| paper | d4-conf-ecai-2025-0186 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; every valid instance has a core payoff, constructible in \(\operatorname{poly}(m,\tau,L)\) time. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 2
Given a finite compatibility graph \(H=(U,F)\), a finite set of center types \(T\), rational masses \(\mu_t\ge 0\) summing to \(1\), and per-center supplies \(b_t\in\mathbb{Q}_{\ge 0}^{U}\), define each coalition mass \(x\in[0,\mu]\) to have supply \(s_u(x)=\sum_{t\in T}b_{t,u}x_t\) and worth \(\nu(x)=\max\{\sum_{\{u,v\}\in F}z_{uv}: z_{uv}\ge0,\ \sum_{e\ni u}z_e\le s_u(x)\ \forall u\in U\}\). Decide whether there is a nonnegative type-payoff vector \(p\) such that \(\sum_t\mu_t p_t=\nu(\mu)\) and \(\sum_t x_t p_t\ge\nu(x)\) for every coalition mass \(x\in[0,\mu]\).
A distribution \(\mu\) over exchange-center types, each with per-center supplies \(b_t\) to compatibility classes in a fixed finite graph \(H\). Coalition choices are mass vectors \(x\); worth is fractional matching mass \(\nu(x)\); the decision variables are type payoffs \(p_t\), constrained to sum to grand-coalition worth and cover every coalition's worth. The dual of the grand-coalition matching LP gives a feasible payoff vector.
The small-support case assumes centers share a finite block-structured compatibility graph, and the paper's general kidney-exchange motivation does not establish how prevalent that regime is.
fatal: False
Covers the paper's \(\mathrm{coNP}\)-containment result for partitioned maximum-matching core existence; it leaves the cited hardness component and the paper's other results untouched.
The strongest mirror I see is for the paper’s partitioned maximum-matching game, motivated by kidney exchange. A plausible high-multiplicity setting is a large exchange network with many participating clinics or centers, but relatively few distinct profiles of patient-donor pairs and compatibility patterns. A type records a center’s complete per-capita contribution to those compatibility classes; clinics of the same type are interchangeable. Thus the number of centers can be large while the support size \(\tau\) stays small. The paper’s kidney-exchange precedent makes this setting especially credible.
My anchor is Proposition 2 (labelled lem:PMGcoNPcontain in the text). Proved in this paper, it says that deciding whether a partitioned maximum-matching game has a core allocation belongs to coNP. The paper’s Table 1 gives the problem as coNP-complete: the hardness is cited from Biró et al. (2019), while this paper proves the containment by giving polynomially checkable certificates for no-instances. Those certificates encode the ellipsoid procedure’s violated coalition constraints, which can be checked using polynomial-time maximum-matching computations. This anchor is therefore a coNP upper-bound result, with cited hardness as context; it is not a hardness theorem proved by this paper.
Here is the continuous question I would hand to a prover: Atomless Partitioned-Matching Core Existence (APMCE). An instance consists of a finite compatibility graph \(H=(U,F)\), a finite set \(T\) of center types, rational type masses \(\mu_t\ge 0\) summing to \(1\), and a rational contribution vector \(b_t\in\mathbb{Q}_{\ge 0}^{U}\) for each type. A coalition is represented by a mass vector \(x\) with \(0\le x_t\le\mu_t\). It supplies \(s_u(x)=\sum_{t\in T}b_{t,u}x_t\) mass of compatibility class \(u\). Its worth is the maximum matched mass
\[
\nu(x)=\max \sum_{\{u,v\}\in F} z_{uv}
\quad\text{subject to}\quad
z_{uv}\ge 0,\qquad
\sum_{e\ni u}z_e\le s_u(x)\ \text{for every }u\in U.
\]
The question is whether there are nonnegative per-center type payoffs \(p_t\) such that \(\sum_t\mu_t p_t=\nu(\mu)\) and, for every coalition mass vector \(x\), \(\sum_t x_t p_t\ge\nu(x)\). A solution is such a payoff vector.
I expect this mirror to be tractable—indeed, core existence always holds in this model. The dual of the matching LP has variables \(y_u\ge0\) with \(y_u+y_v\ge1\) for every compatibility edge. Choose an optimal dual solution for the grand coalition and set \(p_t=\sum_u b_{t,u}y_u\). Duality gives equality for the whole population, and weak duality gives the required inequality for every coalition. The dual LP also constructs the allocation in polynomial time in the graph and type descriptions and their bit lengths.
This is a plausible continuation of the authors’ problem because the players remain organizations, coalition worth remains matching worth, and core stability remains the question. The model co-modifies the matching representation: an atomless coalition supplies fractional mass of patient-donor classes, and its matching can split that mass. That is the natural aggregate limit when many exchangeable pairs are pooled. The paper’s cited high-multiplicity kidney-exchange work supports the regime; it does not make this continuous model a prior-art collision.
The mirror covers only core existence for partitioned maximum matching. It does not mirror the paper’s core-verification, vertex-cover, dominating-set, spanning-tree, or individual-rationality results. Further questions include how the continuous allocation yields additive approximations for large finite populations, and how the conclusion changes when compatibility profiles or center contributions cannot be compressed into a small set of types.
The weak point is that Proposition 2 itself proves only coNP containment; the hardness side comes from cited work. Also, APMCE replaces each coalition’s integral matching value with fractional matching on aggregate supply. If the authors or a referee require coalition worth to remain integral for every coalition, this is a relaxation rather than their direct limit. The case for accepting it rests on the high-multiplicity regime and on fractional matching being the natural aggregate value when individual pairs are exchangeable.
The strongest objection is to the proposed model’s compression. Proposition 2 (lem:PMGcoNPcontain) is a real computational result: it proves coNP containment for core existence in the partitioned maximum-matching game, though the hardness in the table comes from cited work. Its continuous mirror is therefore a legitimate anchor.
In APMCE, a type’s vector \(b_t\) records how much supply it contributes to each compatibility class, and \(H\) fixes compatibility between classes. That captures only block-structured compatibility: units in a class interact according to the same fixed pattern. In the paper’s general graph, two organizations with the same counts of vertex categories can still have different compatibility links, which affect coalition worth. A complete type must include those links. For arbitrary networks, that can make the support grow with the instance, defeating the proposed small-\(\tau\) regime.
The best repair is a repeated, finite-type exchange network where compatibility really is determined by the classes. There, fractional matching is a credible aggregate limit, and the matching dual yields type payoffs satisfying the core inequalities. The model preserves population continuization and asks the paper’s core-stability question. The resulting tractability is not a reason to dismiss it under this programme’s standards.
So the negative case rests on how common and compelling that regular-network regime is. Many exchange networks have individualized compatibility, and the paper’s motivating players are organizations, whose number may be modest even when they own many pairs. But repeated compatibility profiles across many organizations remain plausible. I cannot honestly rule out a worthwhile mirror in every scenario; this objection weakens the proposed scope, but it does not defeat the 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.