| paper | d4-conf-ijcai-2009-0284 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: Polynomial-time solvable under the stated explicit representation. Maximizing welfare over at most \(\min\{2,K\}\) nonzero blocks always achieves at least \(\mathrm{OPT}/K\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu\) summing to one, a coalition-slot limit \(K\), and explicit rational piecewise-linear nonnegative coalition values \(u(x,\Pi)\) satisfying positive externalities, find a feasible mass partition \(\Pi=\{x^1,\ldots,x^r\}\), with \(r\le K\) and \(\sum_j x^j=\mu\), whose value \(W(\Pi)\) is at least \(\mathrm{OPT}/K\). Can this guarantee be achieved by optimizing over the one- and two-block mass partitions?
A normalized mass vector \(\mu\) describes suppliers by complete payoff-relevant type. A feasible coalition structure partitions that mass into at most \(K\) blocks; its value is \(W(\Pi)=\sum_{x\in\Pi}u(x,\Pi)\), with values depending on the aggregate type masses and the full structure. The approximation task is to return a structure with value at least \(\mathrm{OPT}/K\).
The mirror covers the \(PF^+\) approximation guarantee in Theorem 3 for societies with at most \(K\) coalition slots. It leaves the \(PF^-\) guarantee, preprocessing and anytime algorithms, experiments, and unrestricted partition-function games aside.
The strongest numbered anchor is Theorem 3, proved in this paper. For a \(PF^+\) game, it says that searching every coalition structure with at most two coalitions suffices to guarantee a solution within ratio \(\beta=n\) of optimal; those structures number \(2^{n-1}\). The paper’s separate NP-completeness claim is cited from Sandholm et al. and concerns CFGs, so I would not use it as an anchor for this \(PF^+\) mirror.
A plausible regime is a large ecosystem of small suppliers forming R&D or procurement consortia. Suppliers share a finite set of payoff-relevant types—technology, costs, role, and responses to other coalitions—while the number of suppliers is much larger than the number \(\tau\) of types. Merging two consortia might, for example, create a shared standard that benefits the other consortia. Suppose the ecosystem has at most \(K\) consortium slots. A type is the complete payoff-relevant profile; \(\mu_t\) is the fraction of suppliers of type \(t\); and \(x^j_t\) is the mass of type \(t\) assigned to consortium \(j\). Each supplier belongs to one consortium; fractional mass records the distribution across many such suppliers.
I would call the resulting question Positive-Externality Mass CSG-\(K\). An instance gives a finite type set \(T\), rational masses \(\mu\in\mathbb{Q}_{\ge0}^{\tau}\) summing to one, the slot bound \(K\), and nonnegative coalition-value functions \(u(x,\Pi)\). A feasible structure is a finite collection \(\Pi=\{x^1,\ldots,x^r\}\), for \(1\le r\le K\), with \(\sum_j x^j=\mu\). Its value is \(W(\Pi)=\sum_{x\in\Pi}u(x,\Pi)\). Require positive externalities in the paper’s sense: merging two blocks other than \(x\), while leaving \(x\) intact, cannot lower \(u(x,\Pi)\). For a concrete finite input, give the value functions as rational piecewise-linear rules over their mass-vector domains, with explicit polyhedral cells.
The task is to return a feasible \(\Pi\) with \(W(\Pi)\ge \mathrm{OPT}/K\), where \(\mathrm{OPT}\) is the best value over all feasible structures. This is a direct mass analogue of Theorem 3’s search guarantee. For any block \(x\) in any structure, merging all the *other* blocks gives the two-block structure \(\{x,\mu-x\}\); positive externalities mean \(u(x,\Pi)\le u(x,\{x,\mu-x\})\). If \(B\) is the best two-block structure, nonnegative values give \(u(x,\Pi)\le W(B)\). Summing over at most \(K\) blocks yields \(\mathrm{OPT}\le K W(B)\). In the stated piecewise-linear encoding, finding \(B\) reduces to maximizing the two-block objective over \(0\le x\le\mu\), which can be done by optimizing over its listed polyhedral cells. I therefore expect this approximation problem to be Class A for that encoding. The full objective with more blocks could still be harder.
This mirror covers the paper’s \(PF^+\) worst-case approximation result, not its \(PF^-\) guarantee, experiments, or all unrestricted PFGs. Its weakest point is the cap \(K\): the paper allows up to \(n\) coalitions, whereas the mirror needs a finite number of consortium slots to retain a useful bound as the population grows. That cap is a real restriction, but it leaves the paper’s central question intact—choosing a partition when coalition value depends on the other coalitions—and is plausible in settings with a fixed number of available consortiums. Removing the cap, or finding conditions that give a useful bound as it grows, is a natural next question.
Theorem 3 is a genuine computational anchor: it gives a worst-case approximation guarantee for \(PF^+\), so the “no named result” objection does not apply.
The strongest objection is about whether a useful type space preserves the paper’s model. Its partition-function values may depend on the identities of agents across the whole coalition structure. A finite type description works only when agents with the same type are interchangeable in every coalition and under every externality. In the supplier example, compatibility, patents, or market overlap could make those interactions individual-specific; encoding them in types could make \(\tau\) grow with the population. The proposed mirror therefore needs a substantive case that its finite types capture all payoff-relevant interactions, not just suppliers’ broad roles.
That objection does not defeat the best version of the mirror. In an anonymous setting where coalition values depend only on type masses and structure, the mass model is coherent, and the \(K\)-block bound follows from the same positive-externality argument. Fixed consortium capacity is also a plausible regime. I can question whether that restricted model earns a place in the programme, but I cannot honestly argue that no worthwhile scenario exists. The negative case is weak at precisely this 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.