| paper | Approximate Strategyproof Mechanisms for the Additively Separable Group Activity Selection Problem |
| authors | Michele Flammini, Giovanna Varricchio |
| venue | IJCAI 2022 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
For \(k=2\), finite type set \(\Theta\), rational masses \(\mu_\theta\) with \(\sum_\theta\mu_\theta=1\), and rational nonnegative \(p_\theta(a)\) and \(\omega_{\theta,\theta'}\), does there exist one deterministic copyable-grouping mechanism for every such society that is individually strategyproof on every finite replica realizing \(\mu\) and has \(\sup_I \operatorname{OPT}(I)/\operatorname{SW}(M(I))\le B\) for some finite \(B\)?
Use an atomless population \((\Omega,\lambda)\) of mass \(1\), summarized by \((\Theta,\mu)\). Type \(\theta\) contains the complete activity vector \(p_\theta\) and interaction row \(\omega_{\theta,\theta'}\). A measurable grouping \(\mathcal P\) assigns each group an activity, with \(u_x=p_{\theta(x)}(a(G))+\int_G\omega_{\theta(x),\theta(y)}\,d\lambda(y)\) and normalized utilitarian welfare \(\operatorname{SW}=\int_\Omega u_x\,d\lambda(x)\). Strategyproofness is imposed through the canonical finite-replica lift; the mechanism may use null singleton groups because activities are copyable.
Individual strategyproofness is not intrinsic to \(\mu\) alone: the mirror depends on a finite-replica lift, and \(M4_\infty\)'s singleton branch uses null groups in the atomless partition.
fatal: False
The mirror covers the copyable non-negative regime of Theorem 1 and the exact \(M4\) guarantee of Theorem 9, while leaving the other preference, weight, anonymity, and non-copyability regimes untreated.
The best positive case is a faithful mechanism-design mirror, not merely a population interpretation of group activity selection. My lead anchor is Theorem 1, proved in this paper:
No bounded deterministic strategyproof mechanism exists with non-negative preferences and weights, even when \(k=2\) and activities are copyable.
The paper has no numbered NP-hardness theorem of its own; the NP-hardness of optimal allocation is only cited from Bilò et al. (2019). Theorem 1 is therefore the strongest available hardness-style anchor.
The continuous model is as follows. Let \((\Omega,\lambda)\) be an atomless population of total mass \(1\). There is a finite type set \(\Theta\), with \(\mu_\theta=\lambda(\{x:\theta(x)=\theta\})\). A type \(\theta\) consists of a complete activity-preference vector \(p_\theta:A\to\mathbb R_{\ge0}\) and an interaction row \(\omega_{\theta,\theta'}\ge0\) describing the value that an agent of type \(\theta\) places on an agent of type \(\theta'\). Thus two agents have the same type exactly when they are indistinguishable in both activity preferences and interpersonal weights.
Because the paper’s strongest results concern copyable activities, an outcome is a measurable partition \(\mathcal P\) of \(\Omega\) into groups, with each group \(G\in\mathcal P\) assigned an activity \(a(G)\in A\). Several groups may perform the same activity. If \(x\in G\), its utility is
\[ u_x(\mathcal P) = p_{\theta(x)}(a(G)) + \int_G \omega_{\theta(x),\theta(y)}\,d\lambda(y). \]
The objective is normalized utilitarian welfare,
\[ \operatorname{SW}(\mathcal P) = \int_\Omega u_x(\mathcal P)\,d\lambda(x), \]
and \(\operatorname{OPT}\) is the maximum of this quantity over all measurable groupings.
This is a genuine high-multiplicity version of AS-GGASP. A finite replica with \(n_\theta\) agents of each type has \(\mu_\theta=n_\theta/n\). Taking discrete pair weights \(w_{ij}=\omega_{\theta,\theta'}/n\) makes the discrete utilities exactly equal to the displayed integral. This is the standard mean-field normalization; if unnormalized pair sums are desired, an explicit population-scale factor can be placed in front of the integral. Since the paper permits arbitrary non-negative weights, this is a legitimate family of instances rather than a change of objective.
The associated lead problem is:
\[ \mathrm{Det\text{-}CAS\text{-}GGASP}_\infty(B). \]
Its input is \(k=2\), a finite type domain with rational masses and rational non-negative \(p\) and \(\omega\), together with a finite approximation bound \(B\). The question is whether there exists a deterministic direct-revelation mechanism \(\mathcal M\) which, for every such society, outputs a grouping, is strategyproof, and satisfies
\[ \sup_I \frac{\operatorname{OPT}(I)} {\operatorname{SW}(\mathcal M(I))} \le B. \]
A solution is a mechanism description satisfying these conditions; a negative solution is a strategyproofness lower-bound family.
Truthfulness must be defined carefully. A literal histogram-only mechanism would make one individual’s report invisible in an atomless population, making strategyproofness vacuous. I would therefore require finite-replica consistency: for every rational type distribution and every finite replica realizing it, an individual may change its reported \(p\)-vector and interaction row, changing the induced \(1/n\)-mass profile, and the mechanism must not increase that individual’s true utility. This retains the paper’s individual-report interpretation while taking the high-multiplicity limit.
I expect Theorem 1’s obstruction to transfer. Its proof uses only two activities, copyable grouping, non-negative values, and a local incentive gadget with an arbitrarily large weight \(M\). The combinatorics do not live in the number of named agents. Replacing repeated agents by positive-mass cohorts and replacing sums by integrals should preserve the incentive conflict. This would be a transferred impossibility, not continuum-specific hardness: the continuum does not dissolve the obstruction because it is already present at the level of a two-activity local gadget.
The plausible regime is a large standardized workforce: perhaps \(10^5\) employees assigned to copyable projects, with \(\tau\) cohort types determined by job family, task-preference vector, and team-affinity profile. The number of individuals is huge while \(\tau\) might be in the tens or hundreds. The paper’s own workers-and-teams interpretation fits this directly. The continuous problem preserves every substantive ingredient of the authors’ problem: private activity preferences, private interpersonal weights, grouping, copyable activities, strategyproofness, and utilitarian welfare.
As a constructive cross-check, I would also anchor the mirror on Theorem 9, proved here:
Mechanism \(M4\) is strategyproof for copyable activities and non-negative preferences and weights, with approximation ratio \(2-\frac1k\).
The corresponding continuous problem, \(\mathrm{Copyable\text{-}AS\text{-}GGASP}_\infty^{\mathrm{SP}}\), is: given a finite-support continuous society with \(k\) activities, output a randomized strategyproof grouping mechanism with ratio at most \(2-\frac1k\).
The solution is exactly the paper’s mechanism \(M4\):
The mechanism is well-defined for a continuum, and its strategyproofness is unchanged. For the welfare proof, write welfare as interaction welfare \(X\) plus preference welfare \(Y\). If \(z_1\) is the first outcome and \(z_2\) the singleton outcome, then
\[ X(z_1)=W,\qquad X(\operatorname{OPT})\le W, \]
where \(W\) is the total interaction integral,
\[ W=\iint_{\Omega\times\Omega} \omega_{\theta(x),\theta(y)} \,d\lambda(y)\,d\lambda(x). \]
Moreover,
\[ \mathbb E[Y(z_1)]\ge \frac{1}{k}Y(\operatorname{OPT}), \qquad Y(z_2)\ge Y(\operatorname{OPT}). \]
The paper’s algebra therefore carries over verbatim with sums replaced by integrals, giving
\[ \frac{\operatorname{OPT}} {\mathbb E[\operatorname{SW}(M4)]} \le 2-\frac1k. \]
The bound remains tight in the continuous model: take \(k\) preference types, each of mass \(1/k\), with type \(i\) valuing only activity \(a_i\), and set all interaction weights to zero. Thus this is not a weakened problem engineered to become easy. It is the same mechanism and the same objective in a genuine high-multiplicity regime. Its computation is tractable in \(\operatorname{poly}(k,\tau,L)\), since the mechanism only scans the explicit type vectors and returns a two-outcome lottery.
These two anchors give a meaningful continuous landscape: the deterministic problem should inherit the impossibility of Theorem 1, while the randomized copyable problem admits the exact continuous analogue of Theorem 9. They also generate worthwhile follow-up questions:
The weakest point is the truthfulness convention. Without an explicit finite-replica or infinitesimal-deviation requirement, strategyproofness in an atomless population can become vacuous. The normalization of interaction weights is a second, smaller modelling choice. But both choices are transparent, preserve the paper’s utility formula under a precise high-multiplicity dictionary, and keep the authors’ actual mechanism-design question intact. If a referee rejects that convention, the constructive welfare mirror from Theorem 9 still stands, but the transfer claim for Theorem 1 becomes weaker.
The strongest objection is not that a large workforce lacks multiplicity. The proposed cohort story is plausible. The problem is that the paper’s central object is individual strategyproofness, whereas the programme’s continuous society is only a distribution \( \mu \).
A unilateral report by an atomless individual changes no mass and hence changes neither \( \mu \) nor any integral computed from it. Any mechanism whose input is genuinely only \( \mu \) therefore makes strategyproofness vacuous. The proposed “finite-replica consistency” does not repair this: it quantifies over a family of finite mechanisms and asks how an individual is embedded into each replica. That is an asymptotic dictionary, not a mechanism defined on the continuous society. Moreover, one deviation creates a new type of mass \(1/n\), so the fixed finite type space is no longer the whole strategic domain.
This breaks the claimed transfer of Theorem 1. Its proof is an individual-level local-gadget argument: Lemma 1 uses a named agent’s utility and an arbitrarily large weight \(M\) to force a particular assignment. Replacing sums by integrals preserves aggregate welfare, but it does not preserve such pointwise incentive constraints. A named agent and a named incident edge have zero mass in the limit. Replacing them by positive-mass cohorts changes unilateral truthfulness into coalition or representative truthfulness. That may be an interesting new model, but it is not Theorem 1’s mechanism-design problem. The same objection applies even more directly to Theorem 3, whose lower-bound witness is a single agent \(x\) whose expected number of co-participants is compared across reports.
Theorem 9 is the stronger anchor, but it also depends on this fault line. Mechanism \(M4\)’s second branch assigns every agent to a singleton group. In an atomless population this is an uncountable partition into null groups. If null groups are admitted, the entire interaction component disappears in that branch and the mechanism reduces there to a pointwise “choose your favourite activity” rule. If groups must have positive mass or a finite representation, the branch is unavailable; approximating it by microgroups reintroduces a finite scale and no longer gives the exact paper mechanism. One can restore the pointwise rule by retaining a labelled field \(x\mapsto\theta(x)\), but then the model is no longer a distribution-only society: it has reinstated the individual structure that continuization was supposed to aggregate.
So the negative case is that the proposed mirrors alternate between two failures: distribution-only models make individual strategyproofness vacuous, while pointwise or finite-replica models retain the discrete strategic object. The formal welfare inequality for \(M4\) survives integration, but that is not enough to establish a worthwhile continuous mechanism-design problem.
This case is not airtight. If ChoCo explicitly accepts measurable type fields, singleton microgroups, and finite-replica-consistent truthfulness as its mechanism-design convention, then \(M4\) is a legitimate mirror and the universal negative claim fails. The defensible conclusion is narrower: the proponent has not yet shown that Theorem 1—or the strategyproofness aspect of Theorem 9—survives in the programme’s canonical distributional model.
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.