| paper | d4-journals-jair-2010-0012 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard; in fact undecidable, even for \(m=\tau=1\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5.4
statement extracted from the paper’s text layer
Given finite types \(T\), rational masses \(\mu_t>0\) summing to \(1\), rational type-level payoff constraints \(P\) and their projections \(P_I\), reservation payoffs \(r_t\), and an exact evaluator \(V(q)\) for rational coalition masses \(q\in[0,\mu]\), determine whether there is a grand-coalition allocation \(x\in P_T\) with \(\sum_t\mu_t x_t\le V(\mu)\) and \(x_t\ge r_t\), that is efficient under the paper's definition (no feasible \(y\) has \(y_t>x_t\) for every type) and admits no blocking coalition: there are no nonzero \(q\) and \(p\in P_{I(q)}\) such that \(\sum_{t:q_t>0}q_t p_t\le V(q)\) and \(p_t>x_t\) for every type with \(q_t>0\).
A continuum of interchangeable agents grouped by complete type, with mass \(\mu_t\) per type, type-level payoff averages constrained by \(P\), and coalition worth \(V(q)\) for each mass profile \(q\). Core nonemptiness asks whether some feasible, individually rational, Pareto-maximal grand-coalition allocation has no strictly improving feasible mass coalition.
The proponent's condition [?] assumes the full worth is allocated, while the paper defines efficiency by Pareto maximality, which can hold below total worth under nonconvex constraints; the mirror question below uses the paper's Pareto maximality condition.
fatal: False
The mirror covers core nonemptiness from Theorem 5.4. It leaves the core and bargaining-set checking results, bargaining-set nonemptiness, and the analytical results on other solution concepts unaddressed.
The strongest case is a continuous analogue of core nonemptiness for constrained coalitional games. A fitting regime is a large service cooperative with many interchangeable workers in each skill, cost, and availability class. A type records the full profile the game uses; \(\mu_t\) is that type’s share of the workforce. A coalition can recruit any mass of each type, and its worth is the production value \(V(q)\) of that mass profile. Thus the population is the continuous object, while the paper’s central question—whether there is a stable payoff allocation—remains intact.
My lead question is Mass-Constrained Core Nonemptiness. An instance gives a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), rational per-type reservation payoffs \(r_t\), a rational linear system \(P\) constraining type-level average payoffs, and a succinct exact evaluator \(V(q)\) for rational coalition profiles \(q\in[0,\mu]\). Restricting initially to cohesive worth functions means \(V(q)\ge\sum_j V(q^j)\) whenever \(q=\sum_j q^j\). For a set \(I\subseteq T\), write \(P_I\) for the projection of \(P\) onto those types’ payoff coordinates.
A candidate grand-coalition allocation \(x\) must satisfy \(x\in P\), \(x_t\ge r_t\), and \(\sum_t\mu_t x_t=V(\mu)\). A coalition of mass \(q\ne0\) can block it if there is a payoff vector \(p\in P_{I(q)}\) with \(\sum_{t:q_t>0}q_t p_t\le V(q)\) and \(p_t>x_t\) for every type with \(q_t>0\). The question is whether any such \(x\) has no blocking coalition; a solution is such an allocation, or a “no” answer. This retains the paper’s core and its projected linear payoff constraints, while allowing fractional coalition masses and type-level averages.
The anchor is Theorem 5.4, proved in this paper: deciding whether the core is nonempty is \(\Sigma_2^P\)-hard even for cohesive constrained games with polynomial-time worth oracles, with no integer variables and no auxiliary variables. The reduction is from validity of a quantified Boolean formula of the form \(\exists X\,\forall Y\,\Phi\). So the anchor is a hardness result about the paper’s underlying solution concept, not about its encoding. The authors should recognize the mirror: it asks whether a constrained coalitional game has a core allocation, with deviations now drawn from a continuum of type masses.
My forecast is hardness transfer (Class B) for an endpoint-faithful subclass. In the reduction, the combinatorics live in which literal-role players join a coalition, not in the population count. Replacing each role by a large cohort of agents sharing that role preserves the high-multiplicity setting, and the type support can remain much smaller than the population. The proof obligation is to extend worths from whole-role coalitions to fractional masses without creating new blockers or losing the old ones. The theorem alone does not discharge that obligation. For worth functions with efficient convex separation, a tractable subclass is also plausible.
The mirror covers core nonemptiness for the paper’s real-valued constrained games; it does not try to continuize every solution concept. Its weakest point is the extension from a finite characteristic function to \(V(q)\) over every rational mass profile. The paper supplies no canonical interpolation, and fractional coalitions may change core existence. That is a real open modeling and complexity question, but the continuous problem is still a recognizable core question rather than a change of outcome space or a rephrasing of the finite instance.
The named anchor is real: Theorem 5.4 proves \(\Sigma_2^P\)-hardness of core nonemptiness under the stated restrictions. So the decisive “no computational result” objection is unavailable.
The strongest criticism is that the proposed mass model is a redesign, not a direct high-multiplicity version of that theorem. In the paper, worths are given by an oracle on named-player coalitions, and the reduction reads a Boolean assignment from which literal-role players are present. The proposed model instead gives every member of a type one payoff \(p_t\), and makes worth depend on a fractional mass profile. That assumes equal treatment within each type and supplies a new worth function \(V(q)\); neither follows from the theorem. It also imposes \(\sum_t\mu_t x_t=V(\mu)\), whereas the paper defines efficiency by Pareto maximality. Its nonconvex constraints make those conditions differ.
A more faithful model could retain individual payoff variation and define efficiency and blocking over measurable populations. But then the reduction still needs a worth rule for fractional coalitions. An endpoint extension could preserve its literal-role choices by assigning productive worth only when a role’s full mass participates. That makes the coalition choices effectively all-or-none, so the population adds clones without giving mass a genuinely divisible role. A natural extensive worth function for fractional service teams avoids that construction, but may create or remove blockers; Theorem 5.4 does not determine the complexity of that model. This is a fidelity gap, not an objection based on what the answer might be.
That leaves a credible negative case against calling this a direct, theorem-preserving mirror: its computational content depends on choosing a new population worth model, and the most source-faithful construction suppresses fractional coalitions. But it does not establish that no worthwhile mirror exists. The paper’s own service-composition example gives a plausible high-multiplicity setting with repeated skill and cost profiles. A mass-based core question there is recognizable, and the authors could reasonably regard it as their problem. The honest negative verdict is therefore weak against the universal claim.
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.