| paper | d4-conf-ecai-2008-0090 |
| 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 in \(\tau\) and \(L\): output the globally optimal partition \(\{\mu\}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational mass vector \(\mu\) with \(\sum_{t\in T}\mu_t=1\), and a nonnegative value evaluator \(V(x;\Pi)\) for blocks \(x\in\mathbb{R}_{\geq 0}^{T}\) in finite partitions \(\Pi\) of \(\mu\), promised that every feasible merge of blocks \(x,y\) into \(x+y\) satisfies \(V(x+y;\Pi')\geq V(x;\Pi)+V(y;\Pi)\) and \(V(z;\Pi')\geq V(z;\Pi)\) for every other block \(z\), output a partition maximizing \(\sum_{x\in\Pi}V(x;\Pi)\).
An anonymous partition-function game over finitely many complete agent types, with population given by rational masses \(\mu\). A coalition is a type-mass vector, coalition structures partition \(\mu\), and the objective is total coalition value; under the promised superadditivity and positive-externality conditions, return the grand coalition \(\{\mu\}\).
The mirror covers Theorem 1’s grand-coalition case for \(\mathrm{PF}^{+}_{\mathrm{sup}}\). It leaves the singleton case, Theorem 2’s coalition-value bounds, the modified search algorithm, and the simulations unaddressed.
The strongest honest case is narrow: lead mirror — Continuous PF\(^+_{\mathrm{sup}}\) Coalition-Structure Generation. The paper’s best anchor is Theorem 1, proved here. It does not label a problem “in P,” but it identifies an exact optimizer for an entire promised class, so the optimum can be returned without searching coalition structures. The theorem’s two cases are: in PF\(^+_{\mathrm{sup}}\), the grand coalition is always optimal; in PF\(^-_{\mathrm{sub}}\), the all-singleton structure is always optimal. If the relevant additivity and externality inequalities are strict, the respective structure is the unique optimum. I would mirror only the grand-coalition case. The paper gives no comparable named hardness result; Theorem 2’s bounds and the later pruning algorithm do not state a complexity classification.
Here is the continuous problem. Let \(T\) be a finite set of complete agent types, with rational masses \(\mu_t\geq 0\) summing to \(1\). A coalition is described by a vector \(x\in\mathbb{Q}_{\geq0}^{T}\), where \(x_t\) is the mass of type \(t\) in that coalition. A feasible coalition structure is a finite multiset \(\Pi=\{x^1,\ldots,x^q\}\) of nonzero vectors whose sum is \(\mu\). Thus agents of a type can be split across coalitions, while every type attribute relevant to coalition values is retained.
Give the game an exact evaluator for per-agent payoffs \(u(x;\Pi)\), promised to satisfy the PF\(^+_{\mathrm{sup}}\) conditions: merging two blocks \(x,y\) weakly raises their combined total payoff, and weakly raises the per-agent payoff of every other block. Write the combined payoff as \(V(x;\Pi)=\|x\|_1u(x;\Pi)\). The question is to find a feasible \(\Pi\) maximizing
\[
W(\Pi)=\sum_{x\in\Pi}V(x;\Pi).
\]
The requested solution is a maximizing partition. For a finite electorate with \(n\) agents, setting \(u=v(C;\mathrm{CS})/|C|\) makes this objective the paper’s total coalition value divided by \(n\), so the normalization leaves the optimizer unchanged.
In this promised problem, \(\Pi^\star=\{\mu\}\) is optimal. Repeatedly merge blocks: superadditivity says the merged block’s payoff is at least the sum of the two old payoffs, and positive externalities say the other blocks’ payoffs do not fall. Hence total welfare cannot decrease, and after finitely many merges the grand coalition remains. Under the corresponding strict assumptions, every proper merge improves welfare, giving uniqueness. The algorithm outputs the one vector \(\mu\); its description is polynomial in the support size \(\tau\) and mass bit length \(L\). The game evaluator may be supplied as a succinct evaluator or oracle, but the guarantee is a promise about its behavior, not a claim that checking the promise is easy.
A credible regime is a large population of autonomous providers forming shared infrastructure coalitions. Types encode all payoff-relevant features—such as capacity, operating cost, location, and access terms—so there may be many providers but relatively few distinct types. Joint operation can create superadditive value, while positive network spillovers benefit providers outside a merger. This is a specialized regime, but it keeps the paper’s central object: choosing a partition when a coalition’s value depends on the other coalitions. The continuum is in the population; the payoff and coalition-formation structure remain recognizable.
I would expect this mirror to be tractable by the same structural argument. The further questions are whether the paper’s PF\(^-_{\mathrm{sup}}\) and PF\(^+_{\mathrm{sub}}\) cases admit useful continuous algorithms, whether the value bounds of Theorem 2 extend to mass-composition vectors, and when allowing type mass to split changes the optimum or its complexity.
The weak point is that this does not show continuous populations dissolving a discrete hardness: the paper’s PF\(^+_{\mathrm{sup}}\) case already has an immediate discrete optimizer. Nor does Theorem 1 need the continuous machinery to obtain its result. So this is a valid, author-recognizable population mirror, but a modest one—a tractability boundary example rather than the programme’s strongest kind of complexity discovery.
The strongest negative case is against extending Theorem 2 and the search algorithm. Their input is a partition-function game whose values may vary with the entire coalition structure. A type distribution \(\mu\) does not specify those values. To make a continuous version computable, one must add a succinct evaluator over mass-valued partitions; for an unrestricted evaluator, there is no finite input description or meaningful running-time bound. If types must preserve every payoff-relevant distinction, the support can grow with the population. This makes a broad complexity result for the paper’s main search problem hard to formulate without imposing substantial new structure.
That objection does not defeat the proponent’s anchor. In an anonymous mass-based PFG, define coalitions by type-mass vectors and impose the continuous counterparts of superadditivity and positive externalities. The same merge argument proves that the grand coalition is optimal, and the output can be written in time polynomial in the description of \(\mu\). This is a coherent population mirror; neither individual identity nor the fact that the result is simple invalidates it. A better evaluator model could make it even more explicit, though it would still be a narrow structural result rather than a complexity analysis of the paper’s search algorithm.
So the honest case against is limited: most of the paper’s algorithmic contribution does not transfer without a new, succinct model of coalition values, and the one clean anchor is modest. But I cannot honestly defeat that anchor under the programme’s rules. It survives as a worthwhile, if small, continuous mirror; claiming otherwise would rely on the very “the answer is trivial” objection the brief rules out.
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.