| paper | d4-conf-atal-2017-0153 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[2]\)-complete parameterized by \(k\); an \(\mathrm{FPT}\) algorithm in \(k\) exists if and only if \(\mathrm{FPT}=\mathrm{W}[2]\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 14
statement extracted from the paper’s text layer
Given a finite activity set \(A\), a finite type set \(T\) with positive binary-rational masses \(\mu_t\) summing to \(1\), activity approvals \(B_t \subseteq A\), and an integer \(k\), does there exist \(x_{t,a} \ge 0\) such that \(\sum_{a \in A} x_{t,a} = \mu_t\) for every \(t\), \(x_{t,a}=0\) whenever \(a \notin B_t\), and exactly \(k\) activities have positive total mass \(\sum_{t \in T} x_{t,a}\)? What is the parameterized complexity with parameter \(k\)?
A continuous society over approval types \(T\), with mass \(\mu_t\) for each type; allocation variables \(x_{t,a}\) distribute each type’s mass among approved activities. The decision is whether all mass can be assigned while exactly \(k\) activities receive positive mass.
Covers Theorem 14’s activity-only perfect-assignment hardness, including its increasing- and decreasing-preference cases; leaves the paper’s stability, envy-freeness, and size-dependent preference results alone.
My strongest positive case is a narrow mirror of Theorem 14, which the paper proves here by reduction from Dominating Set. The theorem says that \(k\)-Perfect-GASP is W[2]-hard, and remains W[2]-hard when all agents have increasing preferences or when all have decreasing preferences. Here \(k\)-Perfect-GASP asks whether everyone can be assigned to an individually acceptable activity using exactly \(k\) activities.
The lead mirror is Continuous \(k\)-Perfect-GASP with activity-only approvals. An instance consists of a finite activity set \(A\), a finite set of types \(T\), positive binary-rational masses \(\mu_t\) summing to \(1\), an approved activity set \(B_t\subseteq A\) for each type, and an integer \(k\). A type approves every attendance level for activities in \(B_t\), and none for activities outside it. A solution is a matrix of assigned masses \(x_{t,a}\ge 0\) such that
\[
\sum_{a\in A}x_{t,a}=\mu_t,\qquad
x_{t,a}=0\ \text{for }a\notin B_t,
\]
and exactly \(k\) activities have positive total mass \(y_a=\sum_{t\in T}x_{t,a}>0\). The question is whether such a complete, individually rational assignment exists. The matrix permits a type’s mass to be split across activities, just as it records a type-level average of individually assigned people.
A plausible regime is a large event or public programme where many attendees fall into cohorts with identical activity eligibility or preferences. The organizer must place everyone while using exactly \(k\) activity formats. There may be \(N\) people but only \(\tau=|T|\) distinct cohorts, with \(N\gg\tau\); the types include the complete activity-approval information relevant to this problem. In the hardness construction, \(\tau\) grows with the graph, so this is not a claim that the type support stays fixed as the instance grows. The continuous input nevertheless represents arbitrarily large cohorts by their masses.
The paper’s reduction gives a direct hardness argument for this mirror. For a graph \(G=(V,E)\), make one type \(t_v\) and one activity \(a_v\) for each vertex \(v\), and set \(\mu_{t_v}=1/|V|\). Type \(t_v\) approves \(a_v\) and the activities \(a_u\) for vertices \(u\) adjacent to \(v\). Ask whether everyone can be assigned using exactly \(k\) activities. The used activities correspond to a size-\(k\) dominating set: every type must put its mass on an approved used activity, so the chosen vertices dominate \(V\). Conversely, a dominating set permits every type to be assigned to an approved activity; each chosen activity can receive positive mass from its own vertex’s type. Splitting type mass fractionally does not remove the covering requirement. Thus this continuous problem is W[2]-hard parameterized by \(k\), by the same agenda-based combinatorics as the paper’s result. I expect hardness to transfer (Class B).
This mirror covers Theorem 14’s perfect-assignment hardness, including its activity-only reduction. It does not claim to capture the paper’s results on stable, envy-free, or combined assignments. Its weakest point is that the reduction uses preferences independent of group size, a restricted but valid GASP case; it does not preserve the richer size-sensitive activity preferences that motivate much of the paper. Still, the authors should recognize the question: it keeps the perfect-assignment requirement and the budget on used activities, while making the population a distribution over complete approval types.
Natural next questions are whether W[2]-hardness persists with genuinely size-dependent approval sets over activity masses, what changes when the parameter is the number of types rather than the number of used activities, and whether continuous versions of stability or envy-freeness have comparable mirrors.
The only anchor is Theorem 14: \(k\)-Perfect-GASP is W[2]-hard, including when approvals depend only on the activity. The strongest case against its proposed mirror is that, in that activity-only version, the masses do no computational work. For a chosen set of \(k\) activities, feasibility reduces to asking whether every type approves at least one chosen activity and each chosen activity can receive positive mass. In the paper’s reduction, each selected activity is approved by its own type, so the second condition is automatic. The assignment variables and mass values disappear; what remains is Dominating Set on the type–activity incidence structure. The hardness comes from choosing activities, not from treating the population continuously.
That makes this a thin continuization: it gives no new role to the distribution beyond labeling the types with weights, and it does not engage the continuous optimization machinery that motivates the programme. But that is not enough to defeat the anchor. The programme explicitly treats agenda-driven hardness as a legitimate Class B result, and the continuous model is still well-posed for large cohorts with identical activity approvals. The fact that the masses can be eliminated is a possible reason to rate the mirror as modest, not a reason to say it is unworthy.
A richer mirror could make masses matter by letting approval depend on activity attendance, such as minimum group sizes or capacity thresholds. That is a plausible high-multiplicity event model, and perfect assignment remains recognizable. Theorem 14 does not establish its complexity, but that is a gap for a new question to investigate, not a modelling obstruction.
So the negative case is weak. I cannot honestly defeat this anchor: the activity-only mirror survives, and a more population-sensitive version also appears plausible.
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.