| paper | d4-conf-aaai-2018-0589 |
| 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}\)-complete, even with hyperedges of size at most three · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given finitely many role types \(T\) with rational masses \(\mu_t>0\) summing to \(1\), a weighted hypergraph on \(T\) of rank at most four defining \(V(y)=\sum_{E\in\mathcal E}w_E\prod_{t\in E}y_t\), nonnegative rational payoff rates \(a_t\) satisfying \(\sum_t\mu_ta_t=V(\mathbf 1)\), and a positive rational threshold \(\varepsilon\), decide whether some participation vector \(y\in[0,1]^T\) has excess \(V(y)-\sum_t\mu_ta_ty_t\ge\varepsilon\).
A large cooperative production society with interchangeable role types of masses \(\mu_t\); a coalition chooses participation fractions \(y_t\), role-level hyperedges determine worth, and payoff rates \(a_t\) determine the proposed efficient allocation. The computational task is to find a coalition of mass fractions with excess at least \(\varepsilon\).
The reduction uses a type for each graph position, so support grows with the graph, and its type-level interaction terms do not preserve the paper’s bounded individual dependency degree under replication.
fatal: False
Covers Theorem 7’s least-core separation hardness for the stated hypergraph family; it does not mirror the paper’s other stability, value-computation, coalition-structure, or dependency-graph results.
The strongest anchor is Theorem 7, proved in this paper. It says that the separation problem for the least-core LP is NP-hard even on a family of hypergraph games whose dependency degree is \(7\) and whose supermodular degree is \(1\). Separation here means finding a coalition with maximum excess \(v(S)-x(S)\), or deciding whether some coalition’s excess crosses a given threshold. The proof reduces from 3-Regular Independent Set: it creates a pair of players for each graph vertex, adds two auxiliary players, gives each vertex pair a positive edge, gives the auxiliary pair a positive edge, and adds a negative rank-four hyperedge for every graph edge. At the proposed imputation, an excess of at least \(k+|V|/2\) exists exactly when the graph has an independent set of size at least \(k\).
A concrete mirror is Continuous Least-Core Separation for Type-Hypergraph Games. A society has finitely many role types \(T\), with rational masses \(\mu_t>0\) summing to \(1\). A coalition chooses a fraction \(y_t\in[0,1]\) of each type, so its mass of type \(t\) is \(\mu_t y_t\). Its worth is specified by a weighted rank-at-most-four hypergraph on the types:
\[
V(y)=\sum_{E\in\mathcal E} w_E\prod_{t\in E}y_t.
\]
The instance also gives rational payoff rates \(a_t\) for a proposed allocation and a positive rational threshold \(\varepsilon\). In the instances of interest there are no singleton terms, \(a_t\geq0\), and the allocation is efficient: \(\sum_t\mu_t a_t=V(\mathbf 1)\). The question is whether there is a participation vector \(y\in[0,1]^T\) such that
\[
V(y)-\sum_{t\in T}\mu_t a_t y_t\geq\varepsilon.
\]
A solution is such a vector \(y\); if none exists, the proposed allocation passes this separation test.
The regime is a large, role-based cooperative production population: many interchangeable participants occupy each of a set of roles, and output or penalties depend on which role combinations participate. Type includes the role and its payoff and interaction rules, so members of a type are indistinguishable in the model. The continuum lets a coalition include any fraction of each role. The question stays close to the paper’s: which coalition is most dissatisfied with a proposed efficient payoff allocation?
The reduction gives a particularly tight hardness argument. Use the paper’s players as role types, set \(\mu_t=1/\tau\), divide every hyperedge weight by \(\tau\), and use payoff rate \(1\) for the vertex-pair roles and \(0\) for the two auxiliary roles. At every integral participation vector \(y=\mathbf 1_S\), the continuous excess is exactly the paper’s excess divided by \(\tau\). Moreover, the excess is multi-affine, so it has a maximum at a corner of the box \([0,1]^T\). Thus the continuous separation problem is NP-hard by the same reduction, even with type-dependency degree \(7\) and positive type-dependency degree \(1\). I expect hardness transfers (Class B): fractional participation does not erase the reduction’s combinatorics. This case covers Theorem 7’s least-core separation hardness for this hypergraph family; it does not claim to mirror every result in the paper.
The weak point is that the paper’s dependency degree is defined between individual players, whereas this mirror defines interactions between role types. In a continuum role model, one participant’s contribution depends on aggregate participation by other roles, potentially involving many individuals; that is not literally bounded individual dependency degree. Also, the reduction’s number of types grows with the graph, so it establishes no hardness at bounded support. I think an author could recognize this as a continuous, role-anonymous version of their least-core separation problem, but might reject it as a mirror of their sparse, identity-specific interaction model. That limitation is why I would keep the claim narrow: the further questions are whether the type-level hardness survives under a defensible bounded-support restriction, and when bounded individual dependencies can be preserved in a genuinely atomless population.
Theorem 7 is a genuine computational anchor: it proves NP-hardness of least-core separation under bounded dependency and supermodular degree. So the strongest objection has to be about whether the proposed continuum preserves that problem, not whether the result is computational.
In the reduction, each player’s position and hyperedge incidence encode a vertex of an arbitrary 3-regular graph. The proposed mirror makes each such position a type, so the support grows with the graph and the construction supplies no natural high-multiplicity regime with a small set of recurring types. More fundamentally, replacing named-player hyperedges with terms such as \(\prod_{t\in E} y_t\) changes what an interaction means: participation by a role now creates aggregate interactions among its cohort and other cohorts. In an atomless population, adding one individual has measure zero, so the paper’s individual dependency degrees no longer describe the model. The proposed degree bound is instead a new, type-level parameter.
A stronger version could describe a large cooperative organization with many interchangeable participants in each role and surplus generated by role-level participation rates. That is a coherent continuous game, and its least-core separation problem could be worth studying. But it is an anonymous multilinear production model whose interaction graph is over roles; the paper’s reduction does not establish that it is the high-multiplicity version of the authors’ player-level hypergraph game. To preserve the original hyperedges more literally, one could replicate whole copies of the finite game and let interactions occur within each copy. Then the copies separate, and the continuum aggregates repeated finite instances rather than creating the proposed cross-role population problem.
That is the best case against the anchor: the reduction’s graph positions are essential, and the proposed continuum turns them into population roles while changing the interaction semantics. The case remains limited. A role-based production game is plausible, and the authors might recognize least-core separation over it as their problem. I can argue that the mirror is insufficiently grounded in Theorem 7; I cannot honestly rule out every worthwhile continuous scenario.
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.