| paper | d4-conf-ecai-2010-0234 |
| 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. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5.2
statement extracted from the paper’s text layer
Given a finite type set \(\mathcal T\), rational masses \(\mu_t>0\) summing to \(1\), and an explicitly encoded rational polynomial \(F\) of degree \(D\), define each admissible finite population of size \(q\) to have \(q\mu_t\) agents of type \(t\) and coalition worth \(qF(x(S))\), where \(x_t(S)=|S\cap A_t|/q\). Compute, for each type \(t\), the limit of the paper’s Pham Do–Norde value for a type-\(t\) agent as \(q\) grows through admissible sizes.
The society is a distribution \(\mu\) over a fixed set of agent types. A coalition with type-mass vector \(x\) has externality-free worth per unit population \(F(x)\); the decision output is the limiting per-agent Pham Do–Norde payoff \(\phi_t\) for each type, with aggregate type share \(\mu_t\phi_t\).
The polynomial worth input replaces the paper’s weighted MC-net language, so Theorem 5.2’s conversion and size bound do not establish an algorithm for this mirror.
fatal: False
The mirror covers the Pham Do–Norde allocation for polynomial type-mass worth functions. It does not extend the weighted-rule conversion to arbitrary games or cover the McQuillin and Myerson computations.
The strongest case is a narrow high-multiplicity mirror of Theorem 5.2, proved in this paper. It says that, given a weighted MC-net \((A,\mathrm{WR})\), Algorithm 1 converts it to simple rules \(R\) from which the Pham Do–Norde values for every agent can be computed in time linear in \(|R|\), using the method of [14]. The conversion takes time linear in the weighted-rule representation’s size, and the resulting rule set satisfies \(|R|\le |A|\times|\mathrm{WR}|\). The paper’s theorem uses [14] as a subroutine; the conversion and its bounds are the authors’ result here. The paper offers no named hardness result, so this algorithmic theorem is the best single anchor.
Here is the mirror I would hand to a prover: Type-Anonymous High-Multiplicity Pham Do–Norde Allocation. An instance has a finite set of types \(\mathcal T\), rational masses \(\mu_t>0\) summing to \(1\), and an explicitly represented rational polynomial \(F(x)\). A type is a complete description of the characteristics the game uses; \(F(x)\) gives the externality-free worth per unit population of a coalition with type-mass vector \(x\), where \(0\le x_t\le\mu_t\). The task is to compute the limiting Pham Do–Norde payoff density \(\phi_t\) for each type.
The limit is defined through finite instances of the paper’s underlying problem. For each sufficiently divisible population size \(q\), create \(q\mu_t\) exchangeable agents of type \(t\). Give a coalition \(S\) externality-free worth \(qF(x(S))\), where \(x_t(S)=|S\cap A_t|/q\). Compute the paper’s Pham Do–Norde value for any type-\(t\) agent and take its limit as \(q\) grows. The problem’s solution is the vector \((\phi_t)_{t\in\mathcal T}\); the type’s aggregate share per unit population is \(\mu_t\phi_t\). For polynomial \(F\), the limit exists and is
\[ \phi_t=\int_0^1 \frac{\partial F}{\partial x_t}(\lambda\mu)\,d\lambda. \]
This is not a new allocation axiom attached to an unrelated problem: each finite approximation uses the same Pham Do–Norde extension as the anchor, and the limit asks what that computation becomes when a society has many agents but few types. The regime could be a large coalition-forming market or consortium with many providers in a small number of contract and contribution categories. Agents within a type share every game-relevant characteristic; if the model uses an additional distinction, it belongs in the type description. Here \(q\) can be very large while \(|\mathcal T|\) stays small.
I expect this mirror to be tractable. If \(F(x)=\sum_\alpha c_\alpha x^\alpha\), then
\[ \phi_t=\sum_{\alpha:\alpha_t>0} c_\alpha\frac{\alpha_t}{|\alpha|}\mu^{\alpha-e_t}, \qquad |\alpha|=\sum_s\alpha_s. \]
Thus the allocation can be computed exactly in time polynomial in the number of polynomial terms, the degree, and the rational input bit lengths, without depending on \(q\). The finite theorem’s bound grows with \(|A|\); this continuous question asks whether type-level structure lets us remove population scale from the computation.
The scope is only the Pham Do–Norde calculation anchored by Theorem 5.2. That extension depends on externality-free values, so this mirror preserves precisely the part of the externality game that the paper’s target uses. It does not claim to continuize the paper’s other two extensions or the weighted MC-net representation as a whole. It raises further questions: do broader classes of type-level rules have tractable limits; how quickly do finite-population values approach the limit; and can corresponding high-multiplicity mirrors be defined for McQuillin’s and Myerson’s extensions?
The weak point is real: Theorem 5.2 concerns named agents and Boolean weighted rules, while this problem uses type masses and a polynomial worth function. The theorem does not establish that this new input language preserves the paper’s representation-specific algorithm. A referee could regard it as a continuous limit of their allocation problem rather than a mirror of their weighted MC-net computation. The positive case rests on the finite-\(q\) bridge: at every finite size, the allocation being computed is exactly their named Pham Do–Norde value, and the limit retains its marginal-contribution meaning.
Theorem 5.2 is a genuine computational result, so the strongest objection cannot be that the paper has nothing to mirror. Nor is high multiplicity implausible for coalitional games: a large consortium with many exchangeable providers is an easy setting to imagine. The objection is narrower: the theorem’s computation is tied to an explicit language of Boolean rules over named agents. Its conversion checks which literal patterns can hold in coalitions of the form \(\{C,\text{singletons}\}\); its size bound grows with the agents and expressions represented. The theorem exposes no separate bottleneck in population size that continuization removes.
The proposed polynomial-worth mirror is coherent, and its finite-\(q\) bridge is real. But it changes the input language. Giving a type-mass worth function \(F\) directly makes the limit a type-level allocation computation; it does not extend the paper’s weighted-rule conversion. A type-anonymous consortium with smooth per-capita worth may well make that a worthwhile question. The issue is that its connection to Theorem 5.2 is the shared Pham Do–Norde value, rather than the computational contribution the theorem establishes.
A more faithful mirror would preserve the paper’s rules under replication of identical types. That reveals a limitation of the polynomial formulation. A conjunction requiring every member of a type to join is a valid finite rule. If the worth is \(q\) only when all \(q\) agents join, each agent’s finite Shapley payoff is \(1\). The corresponding mass-level worth is a jump at full mass: its ordinary derivative vanishes almost everywhere, so the polynomial-gradient formula does not capture that limit. One can include such boundary cases by defining the continuum value through finite-population limits, but then the smooth formula no longer supplies a general mirror. And to represent graded participation in a type compactly, one needs type-count or mass predicates that the paper’s named-literal conjunctions do not provide.
That is the best negative case: the paper’s algorithm is representation-specific, while the clean continuous model replaces its representation and covers only a regular subclass. It weakens the claim that this particular mirror reflects the paper’s computational contribution. It does not establish that no worthwhile mirror exists. A smooth, type-anonymous high-multiplicity game remains plausible, and the finite Shapley values may give it a sound bridge. I would call the negative case weak at precisely that point: the paper supplies no fundamental obstruction to that scenario, and the opponent’s mirror is not defeated merely because it asks a simpler continuous question.
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.