| paper | d4-journals-geb-2024-0036 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. Every valid input admits a rational stable partition with at most \(2m-1\) productive compositions, constructible in \(O((\tau\log(2+\tau)+m\tau)L^3)\) bit operations. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite set of complete claims types \(T\), rational claims \(c_t>0\), rational shares \(\mu_t\) summing to \(1\), a scale \(H>\theta\), and \(\alpha\in(0,1)\), set \(\rho=\theta/H\). Find a finite-support measure \(\nu\) over productive coalition compositions \(z\in\mathbb{R}_{\ge 0}^{T}\) with \(\sum_t z_t=\rho\), and residual masses \(r_t\ge 0\), such that \(\int z_t\,d\nu(z)+r_t=\mu_t\). For each productive composition \(z\), define its CEL payoff \(u_t(z)=\max(0,c_t-\lambda_z)\), where \(\sum_t z_t u_t(z)=\alpha\sum_t z_t c_t\); residual mass receives payoff \(0\). Let \(A_t(y)=\int z_t\mathbf{1}[u_t(z)<y]\,d\nu(z)+r_t\mathbf{1}[0<y]\). Is there a stable such partition, meaning no composition \(w\ge 0\) with \(\sum_t w_t\ge\rho\) satisfies \(w_t\le A_t(u_t(w))\) for every \(t\)? Construct one or report that none exists.
A nonatomic population with type shares \(\mu_t\) and claims \(c_t\), partitioned into productive coalitions of mass \(\rho=\theta/H\) plus residual mass. Decision variables are the coalition-composition measure \(\nu\) and residual masses \(r_t\); each coalition uses the mass-weighted CEL rule, and stability excludes any available mass block whose members all strictly gain.
As \(H\) grows, the threshold \(\rho=\theta/H\) vanishes, so the limiting partition is dominated by same-claim coalitions at proportional payoff and loses the fixed-headcount boundary effect.
fatal: False
The mirror covers the CEL stable-partition construction of Theorem 5. It leaves the general-rule structure results, the CEA constructions, and the single-peaked extensions aside.
My lead is CEL Mass-Stable Partition, anchored in Theorem 5. Theorem 5 says that for every \(\theta\)-minimal proportional generalized claims problem with \(|N|>\theta\), the partition produced by the paper’s \(\theta\)-CEL algorithm is stable: order agents by increasing claims, repeatedly form a coalition from the \(\theta\) lowest remaining claims, and leave the final group of fewer than \(\theta\) agents together. The theorem is proved in this paper, in Appendix §13. It is a constructive algorithmic result, but the paper does not state a complexity class or analyze a compressed input by type. It contains no named hardness result.
The setting I find most convincing is a large consortium funding programme. Its agents could be local labs or public-interest projects; their claims are audited and fall into a small number of standard claim bands. A consortium becomes eligible only once it reaches a minimum size, receives an endowment proportional to the sum of its members’ claims, and divides that endowment by CEL. Here a type is the full funding-relevant description: the claim band and any eligibility or allocation parameters that affect a member’s payoffs. The regime has a large population scale \(H\) and a much smaller number \(\tau\) of types. This is plausible when a national programme has many applicants but a standard schedule of claims. The paper’s own small research-team example is less convincing as a high-multiplicity regime; the larger programme is the better case.
Here is the continuous problem I would hand to a prover. The input is a finite type set \(T\), rational claims \(c_t>0\), rational population shares \(\mu_t\) summing to \(1\), a rational proportionality factor \(\alpha\in(0,1)\), and a population scale \(H\). Fix the paper’s minimum coalition size \(\theta\), and set the productive coalition mass to \(\rho=\theta/H\). A coalition’s composition is a vector \(z\in\mathbb R_{\ge 0}^{\tau}\), where \(z_t\) is the share of the population of type \(t\) in that coalition. A productive coalition has total mass \(\sum_t z_t=\rho\); the remaining mass, of total size less than \(\rho\), can form a residual coalition with zero endowment. The co-modification is necessary: once the population is measured by shares, the discrete threshold of \(\theta\) people becomes a threshold of \(\theta/H\) of the population.
For a productive coalition \(z\), its endowment is \(\alpha\sum_t z_t c_t\). CEL gives each member of type \(t\) the per-capita payoff \(u_t(z)=\max(0,c_t-\lambda_z)\), where \(\lambda_z\) solves \(\sum_t z_t\max(0,c_t-\lambda_z)=\alpha\sum_t z_t c_t\). A candidate solution is a finite-support measure \(\nu\) over productive coalition compositions, plus residual type masses \(r_t\), satisfying \(\int z_t\,d\nu(z)+r_t=\mu_t\) for every type and \(\sum_t r_t<\rho\). The measure records how much mass is assigned to each coalition composition; identical compositions can be stored once with their aggregate weight.
Call this partition stable if there is no blocking mass coalition. Precisely, define the available strictly-gainful mass of type \(t\) for a proposed payoff \(y\) by \(A_t(y)=\int z_t\,\mathbf 1[u_t(z)<y]\,d\nu(z)+r_t\,\mathbf 1[0<y]\). A proposed composition \(w\) blocks if \(\sum_t w_t\ge\rho\) and \(w_t\le A_t(u_t(w))\) for every type. The question is: given the instance, find such a stable \((\nu,r)\), or report that none exists. The solution is an aggregate partition, not just a payoff vector.
I expect this problem to be tractable. The direct candidate is to order types by claim, lay their masses consecutively on an interval, cut it into pieces of size \(\rho\), and aggregate repeated coalition compositions. This is the mass version of Theorem 5’s “take the \(\theta\) lowest remaining claims” construction. With finite support, the compressed output may remain small even when \(H\) is large. The central proof obligation is to show that this quantile construction is stable against every mass block, including blocks larger than \(\rho\); a second is to establish an exact dictionary when the discrete type counts \(H\mu_t\) are integral. I would expect a polynomial-in-\(\tau\) and bit-length algorithm if those steps go through, but that is a conjecture for the mirror, not a bound proved by the paper.
This mirror covers only Theorem 5’s CEL construction and stable-partition question. It does not claim that the paper continuizes outcomes, probabilities, or time, and it does not stretch to CEA or the paper’s general-rule results. Its weakest point is the scaling of coalition size: the continuum version treats coalition composition as divisible mass, whereas the paper’s coalitions contain whole agents. That is a real co-modification, though it tracks the population-share representation and preserves the threshold as \(\rho=\theta/H\). The result is a credible constructive mirror, but it does not furnish the programme’s preferred question of whether discrete hardness disappears: this paper gives us no named hardness anchor to test that against.
Theorem 5 is the strongest anchor, and the proposed consortium example makes a plausible case for repeated claim types. Its difficulty is that the paper’s minimum size is a fixed number of agents, while the proposed continuum measures population as shares. If the population scale is \(H\), the corresponding minimum coalition mass is \(\rho_H=\theta/H\), which tends to zero.
That limit removes the feature doing the work in Theorem 5. With \(\tau\) fixed claim types, sorting agents by claim puts each type in a contiguous block. The \(\theta\)-CEL construction can make pure same-claim coalitions from almost all of each block; only \(O(\tau\theta)\) agents need be in mixed boundary groups or the residual group. In a pure coalition of type \(t\), CEL gives each member \(\alpha c_t\). Thus the exceptional agents’ share vanishes as \(H\) grows, and the proposed mass partition becomes a collection of infinitesimal, same-type coalitions.
At that proportional payoff, no positive-mass coalition can strictly improve every participant: for any proposed composition \(w\), CEL’s budget identity is
\[
\sum_t w_t u_t(w)=\alpha\sum_t w_t c_t.
\]
If every participating type received strictly more than \(\alpha c_t\), the left side would exceed the right. So the limiting stability question loses the paper’s central tension: the fixed-headcount threshold that leaves some agents with zero outside options has disappeared. The coalition compositions in the proposed mirror shrink to zero mass as well.
The best repair is to hold the threshold at a fixed positive share \(\rho\). That avoids vanishing coalitions and could define a coherent mass-stability problem. But it changes the institutional premise: the minimum group size now grows with the population. The paper motivates \(\theta\) with requirements such as a fixed number of researchers or participating countries. A minimum share could make sense in a different setting, but it is a new quota model, not a co-modification forced by representing this paper’s fixed threshold with population shares.
This is a substantial objection to the proposed mirror, but it does not establish the requested universal negative. A population-share threshold may be a sensible problem in its own right, and the authors might recognize it as a worthwhile extension. I cannot honestly rule out every such scenario; the case against this anchor is strongest when the mirror is required to preserve the paper’s fixed-\(\theta\) coalition requirement.
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.