| paper | d4-conf-ijcai-2016-0132 |
| 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: \(\Sigma_2^p\)-complete, even for \(\tau=3\); hence \(\mathrm{NP}\)-hard. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given a finite set of types \(T\), positive rational masses \(\mu_t\) summing to \(1\), a normal ASP module \(P_t\), and a per-agent payoff function \(w_t\) for each type, does there exist a grand-coalition answer set \(M \in AS(P_T)\) whose type payoffs \(x_t=w_t(M)\) are individually rational and efficient, and for which no nonzero submass \(q\), with \(0 \le q_t \le \mu_t\), has a blocking answer set \(M' \in AS(P_{S(q)})\) satisfying \(w_t(M')>x_t\) for every active type \(t \in S(q)=\{t:q_t>0\}\)?
A continuum population of indistinguishable replicas grouped into finitely many complete types. The society is the distribution \(\mu\); a coalition is a submass \(q\), and its ASP feasibility and per-agent payoffs are determined by the active type set \(S(q)\), as in the paper's membership-based semantics. The decision question is whether a grand-coalition answer set is in the resulting mass core.
The mirror covers core nonemptiness from Theorem 6 and, under the corresponding imputation definition, imputation nonemptiness from Theorem 5. It leaves the ASP representation result, other complexity results, and system experiments outside the mirror.
The strongest mirror I believe is a core-existence problem for a continuum of replicas. A type is a complete agent description: its normal ASP module \(P_t\) and its per-agent payoff function \(w_t\). The society is a rational distribution \(\mu\) over a finite set \(T\) of such types. A coalition is a submass \(q\), where \(0\le q_t\le\mu_t\); its active types are \(S=\{t:q_t>0\}\). Following the paper’s membership-based coalition semantics, its feasible per-agent payoff vectors are generated by the answer sets of \(P_S=\bigcup_{t\in S}(P_t\cup\{t.\})\). Thus the mass records how much of each type is present, while the coalition program depends on which types participate.
For a grand-coalition answer set \(M\), write \(x_t=w_t(M)\). Call \(M\) a mass-core answer set if \(x\) is an imputation—individually rational against each type acting alone and efficient among grand-coalition outcomes—and there is no nonzero submass \(q\) and answer set \(M'\in AS(P_S)\) such that \(w_t(M')>x_t\) for every \(t\in S\). Core-Exists\(_\infty\) asks whether such an \(M\) exists; a solution is a witnessing grand-coalition answer set. This is about a continuous population of agents and coalition deviations, not continuous payoff outcomes.
My lead anchor is Theorem 6, proved in the paper. It states that CAS-NONEMPTY[\(h\)] is \(\Sigma_2^P\)-complete on normal environments for every fixed \(h\ge3\) and for the unrestricted case; hardness holds even with additively separable weight functions. The paper also notes the equivalent core-nonemptiness problem, C-NONEMPTY. Its reduction is from validity of a quantified Boolean formula of the form \(\exists X\,\forall Y\,\Phi\), and already uses three agents.
That three-agent reduction gives a particularly direct continuous lift. Give each of the three roles mass \(1/3\), and make every member of a role share its ASP module and payoff function. In the reduction, the modules are shared across the roles; their different payoff functions distinguish the types. Every positive submass with the same active-role set induces the same coalition program and per-agent payoff possibilities as the corresponding finite coalition. A blocking coalition in one model therefore exists exactly when the corresponding blocking coalition exists in the other. Core existence is preserved. The continuum instance has \(n\gg\tau\), indeed a continuum of agents with just three types, while the quantified formula remains in the program input. I expect this mirror to be hardness-transferring (Class B): the hardness survives replication because it is carried by the ASP description, not by having many distinct agents.
A second worthwhile anchor is Theorem 5, also proved in the paper. It shows that IAS-NONEMPTY[\(h\)] is \(\Delta_2^P\)-complete on normal environments for every fixed \(h\ge2\) and in the unrestricted case, with hardness for additively separable weights. IAS-NONEMPTY asks whether an imputation answer set exists; it is equivalent to imputation nonemptiness, I-NONEMPTY. The paper’s reduction builds on the cited OddLexMaxSAT completeness result. Its two-agent construction similarly gives a two-type mass version: Core-Exists\(_\infty\)’s imputation-only counterpart asks whether any grand-coalition answer set is individually rational and efficient. The same replication argument preserves that question. I also expect hardness transfer here. It is a separate result about the paper’s imputation concept, rather than another way of stating the core result.
These are plausible mirrors of the authors’ problems because they retain the paper’s NTU game, answer-set feasibility, payoff functions, and named solution concepts. Grouping agents by identical programs and payoffs is exactly the high-multiplicity interpretation of type, not a change to the game’s ingredients. A plausible regime is a large service-coordination or task-allocation population with a few role types and shared rules and incentives within each role.
The limitation is real: in this lift, the exact coalition masses do not affect feasibility or payoffs once their support is fixed. A coalition containing any positive mass of a role has the same options as one containing more of it. So this is a clean continuous-population version of the paper’s coalition model, but not a mass-sensitive production model; an extension in which capacities or payoffs depend on \(q\) would be a further question. The mirror covers the paper’s imputation and core existence results, especially Theorem 6. It does not continuize the answer-set encoding itself or the system experiments. Further questions include the complexity of checking a proposed mass-core allocation, whether mass-dependent coalition technologies change the classification, and whether useful algorithms exist when the number of types or the structure of the ASP modules is restricted.
I would not challenge the proponent’s anchors: Theorems 5 and 6 are genuine computational results, and role-based populations are plausible. The negative case is that their proposed lift makes mass irrelevant to the game’s semantics. In the paper, an environment is built from a finite set of named agents. A coalition supplies membership facts and the modules of its members; an answer set then assigns a payoff to each named member. There is no quantity of participants in a type, aggregate resource constraint, or per-capita production function.
Under the proposed type lift, a coalition with mass \(q\) and any other coalition with the same active types produce the same program and the same per-type payoffs. The only question is whether \(q_t>0\), not how large \(q_t\) is. Thus the continuum of possible submasses collapses to the finite collection of active-type sets. The mass-core definition is well-defined as a support-based replica game, but its core question has no population-mass axis to analyze. This is the strongest objection to the specific mirror: a continuum is present in the input, yet it does no work in the coalitional problem.
Theorem 6 remains the strongest anchor. Its \(\Sigma_2^P\)-hardness already fits into three roles, with the quantified formula encoded in the normal ASP program. Replicating those roles creates a continuum of agents, but does not change the answer-set construction or give the formula any mass-dependent meaning. The best faithful lift therefore asks whether that same logical construction has a stable outcome when each role has arbitrarily many indistinguishable copies. That is a coherent question, but it is about replication of a finite role game, not computation over coalition masses. Theorem 5 has the same problem: its two-role OddLexMaxSAT construction can be replicated, while individual rationality still compares the same per-role payoff against the same singleton benchmark. Having positive mass of a role does not alter either comparison.
Giving clones distinct agent identities would preserve the paper’s literal membership semantics, but it does not supply a continuum model: the input and payoff vector grow with the number of identities. To keep a finite description, one must compress clones into types. If that compression is support-based, mass again disappears. A genuinely mass-sensitive version could add capacities, aggregate resources, or answer-set rules parameterized by coalition mass. That may be a good problem, but it adds a production semantics that the paper does not provide. Matching, scheduling, or task assignment could motivate such a model; the paper’s framework alone does not determine how those technologies scale with mass, or which resulting core question its authors would recognize as the same problem.
The proponent is also right that “the reduction uses only three types” is not, by itself, a reason to reject the mirror: high multiplicity with few types is precisely a sensible regime. Nor is the theorem’s hardness a negative point. The objection is narrower: the proposed transfer makes every positive amount of a role equivalent to every other positive amount. The paper has no machinery for making the amount consequential.
So the case against is strongest for the particular core-existence and imputation-existence lifts, and for similar checks of the paper’s solution concepts. It is weaker as a universal claim. If the authors accept a mass-indexed aggregate ASP semantics, a worthwhile continuous core problem could emerge; I cannot rule that out. But that would require choosing and defending a new coalition technology, rather than simply continuizing either theorem’s agent population.
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.