| paper | d4-conf-aaai-2010-0125 |
| 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: exact cutoff evaluation and rational atomic optimal-plan construction belong to \(\mathrm{FP}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
Given a finite type set \(T\), rational population masses \(\mu\), a query mass vector \(x\le\mu\) with \(\lVert x\rVert_1\le\kappa\), and a rational piecewise-affine worth function \(w(q)\) on an explicitly encoded finite union of rational polyhedra of permitted profiles \(q\) with \(\lVert q\rVert_1\ge\delta>0\), compute the maximum welfare and an optimal coalition plan: \[ \operatorname{OPT}_w(x)=\max_{\lambda\ge0}\left\{\int w(q)\,d\lambda(q):\int q\,d\lambda(q)=x\right\}. \] Can this transformed value and plan be computed in time polynomial in |T|, the input bit length, and the profile description, using \(\operatorname{OPT}_w(x)\) below the cutoff and the original worth above it?
A high-multiplicity team formation game with |T| interchangeable agent types, rational type masses, coalition profiles \(q\), and worth \(w(q)\); the decision is a mass-level plan \(\lambda\) over profiles, maximizing \(\int w(q)\,d\lambda(q)\) subject to \(\int q\,d\lambda(q)=x\).
The mirror adds type-composition worths, a piecewise-affine encoding, explicit profile polyhedra, and a positive minimum profile mass, so it does not carry Theorem 4’s computation over to the paper’s arbitrary characteristic functions or microscopic coalitions.
fatal: False
The mirror covers Theorem 4’s truncated small-subproblem computation for composition-based team values; it does not cover the paper’s arbitrary characteristic functions, its approximation guarantees, or its empirical comparisons, and Theorem 1 contributes only a structural analogue.
The best positive case is high multiplicity coalition structure generation. Imagine a very large organization or labor market whose members form project teams or operating units. A type records the traits that affect team value—skills, credentials, role, and costs—so agents of one type are interchangeable. If there are millions of agents but only a modest number \(\tau\) of types, the society is a mass vector \(\mu\), and a coalition’s value can be specified by its type composition. The objective remains the paper’s: partition the population into coalitions to maximize the sum of their values.
My lead anchor is Theorem 4, proved in this paper. It defines \(\nu^k_r(C)\) to equal the optimal coalition-structure value on \(C\) when \(|C|\le kn/r\), and to equal \(\nu(C)\) otherwise. For \(k<r/2\) and \(r\ge2\), Algorithm 1 computes this transformed characteristic function in
\[ O\!\left(\sqrt{nr}\left(\frac{2^k r^r}{k^k(r-k)^{r-k}}\right)^{n/r}\right) \]
time. The theorem is about the preprocessing computation; the paper’s approximation ratios are derived later in the text.
A continuous version is Truncated Mass Coalition Value. Its instance is a type set \(T\), a population mass vector \(\mu\), a query subpopulation \(x\le\mu\) with \(\|x\|_1\le\kappa=k/r\), and an explicitly encoded, rational piecewise-affine worth function \(w(q)\) over permitted coalition profiles \(q\). To ensure a well-defined finite coalition representation, take permitted profiles from a finite union of rational polyhedra with total mass at least a specified \(\delta>0\). A solution is a coalition plan attaining
\[ \operatorname{OPT}_w(x) =\max_{\lambda\ge0} \left\{ \int w(q)\,d\lambda(q): \int q\,d\lambda(q)=x,\ q\le x \right\}. \]
Here \(\lambda\) records the mass-level frequency of coalition profiles. The continuous analogue of the transformed value is \(w^\kappa(x)=\operatorname{OPT}_w(x)\) below the threshold, with the original coalition worth retained above it. The question for a prover is whether this value and an optimal plan can be computed in time polynomial in \(\tau\), the bit length, and the profile description.
This is a configuration LP. Its dual pricing question is to maximize \(w(q)-p\cdot q\) over permitted profiles. With the stated piecewise-affine input, pricing reduces to linear optimization over the encoded polyhedra, so I expect this mirror to be Class A. That is a genuine continuous-population version of the paper’s small-subproblem optimization, not a claim that the paper’s exponential-in-\(n\) runtime itself transfers.
A second, particularly faithful anchor is Theorem 1, also proved here: if \(\nu\) is \(n/r\)-superadditive, it has an optimal coalition structure with at most \(2r-1\) coalitions. Its continuous question is Sparse Mass Coalition Structure. Given \(\mu\) and \(w(q)\), find a welfare-maximizing finite decomposition \(\mu=\sum_j q^j\), under the condition that
\[ w(q+q')\ge w(q)+w(q') \quad\text{whenever }q+q'\le\mu \text{ and }\|q+q'\|_1\le 1/r. \]
Does an optimum exist with at most \(2r-1\) coalition profiles? I expect yes: the paper’s size-based merging argument carries over by replacing \(|C|/n\) with coalition mass. With piecewise-affine worths and fixed \(r\), the resulting bounded-size optimization can be handled by finitely many linear programs. This is a structural tractability result; it does not establish efficient optimization for arbitrary worth functions.
The case covers coalition-structure welfare optimization and its truncated subproblems. It does not claim to mirror every empirical comparison or every approximation guarantee in the paper. I find no numbered hardness result here, so this is a positive case based on the paper’s algorithmic and structural results.
The weakest point is the representation assumption. The paper permits arbitrary values for named-agent coalitions; the mirror groups agents by type and requires coalition value to have a compact composition-based description. That is exactly the high-multiplicity regime, and it is plausible for large teams with standardized roles, but it is a real restriction. The minimum profile mass in the lead formulation also focuses it on macroscopic coalitions. Further questions are whether the truncated-value mirror remains tractable without that cutoff, how much pricing structure natural team-value functions provide, and whether the continuous analogue of Corollary 2’s sharper \(2r-2\) bound holds.
The strongest objection is representational. Theorem 4 is a named algorithmic result, so “there is no computational result to mirror” does not apply. But it computes \(\nu^k_r(C)\) for arbitrary coalitions \(C\), including every size from one agent up to \(kn/r\). In a high-multiplicity model, replacing those coalitions with type-composition profiles requires a worth function on masses. The paper supplies no such function or rule for deriving one: many continuous functions can agree on every composition available in a finite instance and diverge between them.
The proposed piecewise-affine \(w\) makes the continuous problem well-defined, but it adds substantial structure to the paper’s arbitrary characteristic function. Its pricing problem is tractable because the input describes profiles as a finite union of polyhedra and makes worth piecewise affine. That is a legitimate configuration-LP problem for standardized teams. It is a weaker mirror of Theorem 4’s general setting: its tractability comes in part from the new input representation, rather than from carrying over the paper’s truncated dynamic program.
The minimum profile mass \(\delta\) exposes a scale problem. Theorem 4 includes microscopic coalitions; a fixed \(\delta\) omits them. Removing the cutoff can make the continuous welfare unbounded. For example, if every nonempty coalition has worth \(1\), a finite population of \(n\) agents can form \(n\) singleton coalitions. In a divisible population, it can be split into arbitrarily many nonempty coalitions. Requiring worth to vanish proportionally with mass can repair this, but it narrows the model and excludes coalition values whose welfare depends on the number of coalitions. That is a real limit on how faithfully Theorem 4 can be carried over.
This objection does not eliminate the best version of the mirror. A large organization with standardized types and extensive, composition-based team values is plausible, and a continuous truncated-value problem for that class is worth asking. The case against it is that this is a new, regularized high-multiplicity problem, not a general continuation of the paper’s result.
Theorem 1 is harder to defeat. Its merging argument appears to carry over directly: replace coalition sizes by masses and apply the same packing argument. The resulting sparse-decomposition claim is primarily structural rather than a complexity classification, which weakens its fit with ChoCo’s computational emphasis. But that is a matter of priority, not a substantive reason the mirror fails.
So the best negative case is that Theorem 4’s mirror needs extra assumptions and has a genuine small-coalition limit problem. I cannot honestly use it to support the universal claim that no worthwhile mirror exists: the standardized-team setting is credible, and Theorem 1 has a natural continuous form.
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.