| paper | d4-journals-jair-2023-0022 |
| 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 under polynomial-time Turing reductions, already for weighted mass MC-nets. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a rational type distribution \(\mu\) and a finite mass-rule description of a partition-function game, form \(g_q\) by taking \(q\mu_t\) identical agents of each type \(t\), evaluating the rules on coalition masses normalized by \(q\), and computing their finite SS-values. Under the promise that \(A_t=\lim_{q\to\infty,\ q\mu\in\mathbb{Z}_{\ge 0}^{\tau}}\sum_{i:\,\mathrm{type}(i)=t}\mathrm{SS}_i(g_q)\) exists, compute a rational estimate of \(A_t\) within additive error \(\epsilon\).
A society consists of \(\tau\) complete agent types with rational masses \(\mu_t\). A finite rule list maps the focal coalition’s mass vector and the distinct outside coalitions’ mass vectors to partition-function payoffs. The output is the limit of the aggregate SS allocation to a target type in finite replica societies; this is a value-computation problem, with no optimization objective.
The mass-rule semantics is a proposed co-modification rather than one derived from the paper’s named-player literals, and the paper supplies no convergence result for the type aggregate.
fatal: False
The mirror concerns Theorem 5’s SS-value computation and its hardness result. It leaves the MQ-, EF-, HY-, and MY-value results, as well as the paper’s representation-size results, outside its scope.
The strongest case I see is for a continuous version of computing the Stochastic Shapley value. A plausible setting is a large electricity market with many small renewable producers forming balancing cooperatives. Their payoffs depend on the other cooperatives’ formation because of congestion and market-price effects. Producers share a type when their technology, location class, contract, cost schedule, and effect on other coalitions all match. A market may have millions of producers but far fewer such role types; the number of types \(\tau\) can still grow with the instance.
Use a type distribution \(\mu\in\mathbb{Q}_{\ge 0}^{\tau}\), with \(\sum_t\mu_t=1\). A coalition is described by its type-mass vector \(x\), and a partition by a collection of such vectors whose sum is \(\mu\). Give the game by a finite list of weighted rules: each rule tests rational linear conditions on the focal coalition’s mass vector and on the mass vectors of distinct outside coalitions, then contributes its weight if those conditions hold. This is a mass-based counterpart to embedded MC-nets.
The paper’s anchor is Theorem 5, proved in this paper: for games represented as embedded MC-nets or weighted MC-nets, computing the SS-value is #P-hard. Its reduction starts from counting all matchings in a bipartite graph. It constructs an embedded MC-nets game and a player \(i\) for which \(\mathrm{SS}_i=h_G/k!\), where \(h_G\) is the number of matchings in the input graph and \(k\) is the constructed graph’s number of nodes. Thus the theorem establishes hardness for the underlying value computation, not just for an encoding.
My proposed mirror is High-Multiplicity SS Limit. An instance consists of \(\mu\), the finite list of type-mass rules, a target type \(t\), and an additive error \(\epsilon>0\). For each integer \(q\) that makes every \(q\mu_t\) integral, instantiate \(q\mu_t\) identical agents of type \(t\). Evaluate each finite coalition partition using its type masses divided by \(q\), and let
\[ A_{t,q}=\sum_{i:\,\mathrm{type}(i)=t}\mathrm{SS}_i(g_q). \]
On instances where the limit exists, the requested value is \(A_t=\lim_{q\to\infty}A_{t,q}\). A solution returns a rational \(\widehat A_t\) with \(\lvert\widehat A_t-A_t\rvert\le\epsilon\). The mass allocation across coalitions is the structural variable; the objective is the type’s aggregate SS allocation, which averages over coalition partitions under the size-biased formation process. The question is to compute that allocation, not to optimize a coalition structure.
The paper’s authors should recognize the target: it is still computing their SS-value for partition-function games with externalities, now for a high-multiplicity population and a type-level game description. The SS process gives a particularly direct bridge: its premise that a player is more likely to join a larger coalition has a natural interpretation in repeated, size-based coalition formation. The model covers Theorem 5’s SS-value hardness result only; it makes no claim about the other four values or the paper’s representation-size results.
For general instances where \(\tau\) varies, I tentatively expect Class C, continuum-specific hardness. Theorem 5 does not establish hardness transfer: its reduction counts matchings among discrete graph vertices, while the mirror lets type mass split among coalitions. That may dissolve the exact matching count. Still, the limit asks for an expectation over type-mass partitions subject to a compatibility structure, which looks capable of carrying its own computational difficulty. Fixed \(\tau\) or structured compatibility graphs may have tractable cases; determining whether the general problem is hard is part of the proposed programme.
The mirror also raises questions about whether the limit exists for different rule classes, whether exact computation and additive approximation differ, and whether parameters such as \(\tau\) or the interaction graph’s treewidth yield fixed-parameter algorithms.
My weakest point is the bridge itself. The paper defines SS on finite, named players, and its MC-nets rules use named-player literals. The proposed mirror replaces those with conditions on type masses and defines the type’s value through a limit of finite replicas. That is a defensible high-multiplicity continuation, but it is not forced by the paper: different mass-based rule semantics could give different limits, and the paper supplies neither this continuum value nor a convergence result. If the authors reject that co-modification, the mirror fails. The case survives to the extent that it preserves the paper’s central computational question—computing SS allocations in externality-bearing coalition games—while making the population itself, rather than outcomes or uncertainty about a finite profile, the continuous object.
The strongest objection is to how tightly Theorem 5 supports the proposed mirror. Its reduction encodes a bipartite graph using individual players whose roles depend on their incident edges. Those roles generally make the vertices different types. Replicating each type many times turns individual pairings into interactions between masses of role types; the reduction’s matching count no longer carries over directly. Keeping the original player identities preserves the theorem’s model, but offers no population compression. Replacing its rules with predicates on type masses is a plausible new model, though the paper’s theorem says nothing about its complexity.
That objection does not defeat the better mirror. A finite type set with rational population masses, mass-based game rules, and a type’s aggregate SS allocation is a coherent high-multiplicity question. The SS process also gives a natural route to defining the limit through its size-biased coalition formation. For suitably regular rules, one can ask whether the limit exists and how to compute or approximate it. Neither a changed answer nor a changed representation makes that question unworthy under ChoCo’s criteria.
So the negative case is weak at its decisive point. The matching reduction does not establish that Theorem 5’s hardness survives continuization, and it gives little evidence that the proposed limit is computationally rich. But that weakens the anchor’s connection to the paper’s result; it does not show that no worthwhile mirror exists. I cannot honestly rule out a continuous SS computation that the authors would recognize as their problem.
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.