| paper | Group Activity Selection Problem |
| authors | Andreas Darmann, Edith Elkind, Sascha Kurz, J. Lang, Joachim Schauer, G. Woeginger |
| venue | WINE 2012 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.1
statement extracted from the paper’s text layer
Given simple activities \(A\), complete preference types \(T\) with rational masses \(\mu_t\ge0\) satisfying \(\sum_t\mu_t=1\), an allowed-pair relation \(E\subseteq T\times A\), and rational thresholds \(\ell_{t,a}\ge0\) for allowed pairs, decide whether there exist assignment masses \(x_{t,a}\ge0\) and activity masses \(z_a=\sum_t x_{t,a}\) such that \(\sum_a x_{t,a}=\mu_t\) for every type and \(x_{t,a}>0\Rightarrow ((t,a)\in E\land z_a\ge\ell_{t,a})\).
A high-multiplicity a-GASP model with complete threshold and eligibility types, population mass \(\mu\), type-to-activity assignment variables \(x_{t,a}\), activity masses \(z_a\), and a feasibility objective requiring perfect participation.
The mirror covers perfect assignment under increasing preferences in Theorem 4.1 and maximum individually rational assignment for fixed \(p\) in Theorem 4.5. It leaves Nash-stability results, general weak-order GASP, and the paper's other special cases untreated.
The strongest positive case is a population-measure version of a-GASP itself. My lead anchor is Theorem 4.1.
Theorem 4.1, proved in this paper by reduction from X3C, says that deciding whether an instance of a-GASP admits a perfect assignment is NP-complete even when every activity is simple—there is only one copy of each activity—and every agent has increasing preferences. Thus, for every agent \(i\) and activity \(a\), the acceptable group sizes have the form \([\ell_i^a,n]\). A perfect assignment assigns every agent to a non-void activity at an acceptable group size.
A natural continuous mirror is Perfect-a-GASP\(_\infty^{\mathrm{INC}}\). An instance consists of activities \(A=\{a_1,\ldots,a_p\}\), a finite set of complete preference types \(T\), rational masses \(\mu_t\ge0\) with \(\sum_t\mu_t=1\), and rational thresholds \(\ell_{t,a}\in[0,1]\). Type \(t\) accepts activity \(a\) exactly when the final mass assigned to \(a\) is at least \(\ell_{t,a}\). We seek nonnegative assignment masses \(x_{t,a}\) satisfying
\[ \sum_{a\in A}x_{t,a}=\mu_t,\qquad z_a=\sum_{t\in T}x_{t,a}, \]
and
\[ x_{t,a}>0\Longrightarrow z_a\ge \ell_{t,a}. \]
The question is whether such an allocation exists. The output is the mass-assignment matrix \(x\), not a lottery over outcomes: each underlying agent still joins one activity, while \(x_{t,a}\) records the mass of identical agents of type \(t\) assigned there.
This is a sensible high-multiplicity regime for large recurring programmes, corporate training events, or online communities. Millions of participants may fall into a few complete profiles—say department, seniority, budget sensitivity, and tolerance for crowding—while the activities are one-off sessions. Group-size thresholds can naturally be expressed as population shares when activity capacity, staffing, or cost-sharing scales with the size of the programme. A finite \(n\)-agent instance maps directly to this model by replacing \(n_t\) with \(\mu_t=n_t/n\) and an integer threshold \(L_{t,a}\) with \(\ell_{t,a}=L_{t,a}/n\).
The authors should recognize this as their problem: the activities, size-dependent approval, central assignment, simple-activity restriction, increasing preferences, and perfect-participation objective are all preserved. Only the population measure changes from counting agents to mass. It is not continuity in the outcome space.
I would expect the unrestricted continuous problem to be a candidate for Class C rather than an automatic transfer of Theorem 4.1. The X3C reduction does not immediately survive: a type’s mass can be split across several acceptable activities, producing fractional covers that do not correspond to exact covers. But selecting which activities become active, and at what mass thresholds, may remain genuinely combinatorial. For fixed \(p\), or for especially structured thresholds, I would instead expect a Class A result based on enumerating threshold regions and solving flow problems. The resulting boundary—whether activity selection remains hard after individual multiplicity disappears—is exactly the kind of question the theorem makes worthwhile.
A useful supporting anchor is Theorem 4.5, also proved in the paper. It states that an algorithm can find a maximum individually rational assignment for any a-GASP instance in time \((n+1)^p\operatorname{poly}(n)\). The algorithm enumerates the vector of activity group sizes \((n_1,\ldots,n_p)\), and for each vector uses network flow to determine the largest assignment in which every assigned agent approves their activity at that group size.
Its continuous counterpart is Max-IR-a-GASP\(_\infty(p)\). Types have masses \(\mu_t\), and each type-activity pair has an acceptable subset \(S_{t,a}\subseteq(0,1]\), represented by a finite list of rational intervals or breakpoints. We seek \(x_{t,a}\ge0\) maximizing
\[ \sum_{t,a}x_{t,a} \]
subject to \(\sum_a x_{t,a}\le\mu_t\), \(z_a=\sum_t x_{t,a}\), and \(x_{t,a}>0\) only when \(z_a\in S_{t,a}\). Unassigned mass represents the void activity.
For fixed \(p\), this should be tractable: each \(z_a\) lies in one of finitely many breakpoint cells, and after enumerating the \(p\)-tuple of cells, the remaining problem is a capacitated flow or linear program. This is a direct mass analogue of the paper’s \((n+1)^p\) enumeration, with integer group sizes replaced by rational mass regions. The further question is whether the exponential dependence on \(p\) can be reduced, or whether unrestricted activity menus exhibit continuum-specific hardness.
My weakest point is that the continuum changes the combinatorics substantially. In particular, the exact-cover obstruction behind Theorem 4.1 may disappear through mass splitting, and normalized thresholds require a scenario in which group-size economics scale with population. The mirror is therefore not a claim that the paper’s NP-hardness transfers. It is a precise computational question about when that hardness dissolves, and whether the remaining difficulty comes from population multiplicity or from the activity menu itself.
The strongest negative argument is that both proposed mirrors either fractionalize away the paper’s combinatorics or merely re-encode the finite problem with weights. That argument ultimately fails for the lead anchor.
For Theorem 4.1, take an X3C instance with \(3q\) elements. Create one population type \(t_x\) of mass \(1/(3q)\) for each element \(x\). For each set \(Y\), create an activity \(a_Y\), accepted only by the three types corresponding to \(Y\), with normalized threshold \(1/q\). An active activity must receive mass at least \(1/q\), but its entire eligible population has mass exactly
\[ 3\cdot \frac{1}{3q}=\frac{1}{q}. \]
Thus it must receive all three of its eligible types. Since total mass is \(1\), exactly \(q\) activities can be active, and their supports must form an exact cover. Fractional splitting does not help. Repeating each type \(M\) times gives a genuine high-multiplicity interpretation with absolute threshold \(3M\).
So the natural continuous version of Theorem 4.1 is a valid Class B mirror: hardness transfers through a support-preserving normalization. Calling that “just a weighted restatement” is explicitly not an admissible objection under the programme.
Theorem 4.5 is also difficult to defeat. With piecewise-rational acceptable mass intervals, fix a cell for each activity’s mass. Within those cells, the type–activity compatibility graph is fixed, and feasibility is a flow or linear-programming problem. For fixed \(p\), this gives a polynomial algorithm in the number of types and encoding length, replacing the paper’s enumeration of integer group sizes by enumeration of mass cells. The representation requires a natural co-modification, but not an illegitimate one.
The remaining objections are weak. Agents can be recurring cohorts with identical activity thresholds, so multiplicity is meaningful. Group-size thresholds can scale with programme size in settings involving per-capita staffing or cost-sharing. The objective is aggregate participation, not individual identity. Neither the optimum nor the stability notion collapses in the normalized model.
The honest conclusion is therefore that I cannot make a convincing universal negative case. The mirror may not produce a continuum-specific Class C phenomenon—the main hardness can survive intact—but that is a result the programme expressly regards as worthwhile. Theorem 4.1 alone is a credible continuous-population anchor, and Theorem 4.5 provides a second tractable one.
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.