| paper | d4-conf-aaai-2017-0242 |
| 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}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 12
statement extracted from the paper’s text layer
Given a path \(H\) of \(\tau\) cohort types, activities \(A\), rational type masses \(\mu_t\) summing to \(1\), and rational piecewise-linear utilities \(u_t(a,s)\) over activities and group mass \(s\), decide whether there is a core-stable assignment. Represent the assignment by masses \(x_{t,a}\geq 0\) with \(\sum_a x_{t,a}=\mu_t\); require each non-void activity’s users to occupy one connected interval of types. An assignment must be individually rational, and no activity \(a\) may admit a blocking coalition that selects mass from a connected interval, includes all current users of \(a\), and has every selected agent strictly prefer \(a\) at the coalition’s total mass to their current alternative.
A nonatomic extension of group activity selection on a path: each type \(t\) has mass \(\mu_t\) and utility \(u_t(a,s)\); the assignment \(x_{t,a}\) may split type mass across activities, while each non-void activity forms one connected group. Core blocks may select mass from connected intervals and must include all current users of the blocked activity.
The path-hardness instances rely on distinct players in exact positions, while the mirror replaces the individual path with dense cohort layers and extends integer group-size preferences to mass shares; this limits the reduction’s relevance to the mirror’s complexity.
fatal: False
The mirror covers the path clause of Theorem 12. It leaves the theorem’s star and bounded-component clauses, the Nash-stability results, and the fixed-parameter algorithms untouched.
The strongest positive case is for the paper’s core-stability result, because it has a natural mass version: blocking coalitions can contain positive mass, so their incentives do not disappear when the population becomes nonatomic.
The anchor is Theorem 12, proved in this paper. It states that deciding whether a Group Activity Selection Problem with graph structure has a core-stable feasible assignment is NP-complete when the social network is a path, a star, or has connected components of size at most \(3\). The paper proves these hardness results by reductions from Path Rainbow Matching, bipartite Minimum Maximal Matching, and \((3,\mathrm{B2})\)-SAT, respectively; those source problems’ hardness is cited from earlier work. I would rely on the path clause. It is a particularly direct bridge to a continuous population on a path-like network.
Here is the mirror I would hand to a prover: Path-Cohort Core Stability\(_\infty\). An instance has a path \(H\) on \(\tau\) types, a finite activity set \(A\), and rational masses \(\mu_t\geq 0\) summing to \(1\). Each type \(t\) specifies both a preference over activities and group mass, and a position on \(H\). Encode preferences by finite, rational piecewise-linear utility functions \(u_t(a,s)\), for \(a\in A\) and group mass \(s\in[0,1]\), plus a utility for the void activity. This extends the paper’s comparisons over integer group sizes to comparisons over fractions of the population.
The network is a path of dense cohorts: members of a type have identical preferences and network roles, are mutually connected, and have the same links to members of adjacent types. A coalition is feasible when the types it occupies form a connected segment of \(H\). This is a plausible high-multiplicity regime: for example, a long production chain with many interchangeable workers at each of a modest number of stations. The population can grow while the number of types \(\tau\) stays small.
A candidate assignment is a matrix \(x_{t,a}\geq 0\), including a column for void, with \(\sum_a x_{t,a}=\mu_t\). Each person still receives one activity; \(x_{t,a}\) is the mass of type \(t\) receiving it, not a lottery over outcomes. Let \(q_a=\sum_t x_{t,a}\). For every non-void activity, the types with \(x_{t,a}>0\) must form one connected segment. Thus each activity remains single-use: it can be assigned to at most one connected group. Require individual rationality, and call a mass coalition a core block for \(a\) if it selects positive mass from a connected segment of types, includes all current users of \(a\), and every selected person strictly prefers \((a,s)\) to their current alternative, where \(s\) is the coalition’s total mass. The question is whether an assignment exists with no such block; the solution is the assignment matrix \(x\). This matches the paper’s blocking convention that the deviating coalition is connected and contains the target activity’s current group.
I expect this problem to be Class A, provisionally. In the path-of-cohorts model, feasible coalition supports are intervals of types, and a block can be described by mass drawn from those types. That makes a polynomial separation or continuous-feasibility approach seem plausible. The discrete reduction’s choices among named vertices may soften when each cohort can split its mass. That is a conjecture, not an algorithm: single-use activities and the stability constraints could still produce continuum-specific hardness. The natural next questions are whether blocks admit a polynomial separation procedure in \(p,\tau,L\), and whether discrete instances with \(n_t/n\to\mu_t\) have a useful stability-preserving approximation or limit theorem.
The paper’s authors should recognize the question’s core: agents have preferences over activity and group size, groups must be connected, activities are single-use, and the target is core stability. The mirror covers the path hardness clause of Theorem 12; it does not claim to continuize the star or bounded-component clauses, or the paper’s Nash-stability and FPT results. Its weakest point is the network co-modification: a path of dense cohorts is not literally the paper’s path graph. That is also what makes the population genuinely high-multiplicity while preserving meaningful connected coalitions. An author might accept it as a continuous version of their model, but reject it as too different to count as a mirror of the path theorem.
Theorem 12 is a real computational result, and core stability is the paper’s strongest candidate for a continuous mirror. The path clause asks an explicit NP-completeness question about whether a stable outcome exists. So the negative case cannot rest on the absence of a result to mirror, or on the claim that the answer would remain hard.
Its reduction does, however, expose a problem for a faithful high-multiplicity version. The agents encode distinct positions in a Path Rainbow Matching instance: vertex players, edge players, and color activities have different roles, and feasibility depends on their exact locations in the path. In those instances the number of distinct types grows with the instance, rather than with a small set of recurring roles. Repeating bounded components is not an obvious repair. Since each activity can be used by only one group and a connected group stays within one component, with fixed activities and many repeated components the activity-using groups have vanishing population share. Scaling up the activity set avoids that collapse, but also scales up the combinatorial input.
The proponent’s path of dense cohorts is the stronger response. It gives many agents per type and preserves the path’s interval structure at the type level. But it changes the network: identical agents at a position need within-cohort and between-cohort links that turn the path into a path of dense layers. It also replaces preferences over integer group sizes with preferences over population shares. Those are substantial choices, and the paper does not establish that this is the regime its authors would recognize as the same problem. Still, the programme explicitly permits co-modifications forced by population scaling, and a workforce organized into large cohorts along a production chain is plausible. The model is coherent enough that this objection does not defeat the mirror.
So the best case against is that the paper’s hardness theorem itself gives little support for a low-support limit: its hardness is built from named agents and exact network positions. But the improved cohort model escapes that criticism. I cannot honestly rule out a worthwhile mirror of the path core-stability result; the negative case is weak precisely where the proponent’s mass model becomes most credible.
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.