Approximate Strategyproof Mechanisms for the Additively Separable Group Activity Selection Problem

1 Introduction

In the Generalized Group Activity Selection Problem (GGASP) [Darmann et al., 2018] a set of agents and a set of activities are given, and each agent must be assigned to one of the activities according to her preferences. This model can represent several realistic scenarios: workers that split into teams to perform specific tasks, employers to be located in different sites, students assigned to classrooms, and so forth.

Depending on the setting, activities are either copyable or non-copyable. If we consider the problem of splitting tasks among workers, the same task may be performed by different team groups independently; hence, the activities may be assumed to be copyable. On the other hand, students assigned to the same classroom will necessarily stay together, meaning, in this case, that activities are non-copyable.

An interesting subclass of the GGASP is the one with the additively-separable property (AS-GGASP) [Bil`o et al., 2019], in which each agent has preference values and individual weights representing her appreciation for each single activity and for each other agent, respectively. The utility of an agent is given by the sum of her preference for the activity she is assigned to and of her weights for all the other participants. The AS-GGASP has the nice property of being succinctly representable, that is, the input representation is polynomial in the number of the agents. Moreover, it generalizes another widely investigated class of games, the additively-separable Hedonic Games (ASHGs). Such a correspondence actually holds for all classes of GGASP and Hedonic Games (HGs), being HGs the special case in which agents do not care about activities, but only about the agents they are grouped with.

While most of the previous work on GGASP and HGs mostly investigates suitable stability criteria, like Nash and core stability, assuming that agents' preferences are known, in this paper, we focus on the imperfect information setting in which preferences and weights are private information of the agents. A central authority, upon the declaration of such values, must assign agents to activities so as to maximize the social welfare or overall happiness of the agents, while inducing a strategyproof behavior. Namely, given the mechanism proposed by the authority, it must not be possible for the agents to strategically misreport their values to increase their utilities. In other words, truthfully reporting their real preferences and weights is a dominant strategy for all the agents. In addition to strategyproofness and social welfare approximation, anonymity, i.e. the mechanism does not rely on agents' identities, is a remarkable property of a mechanism.

1.1 Our Contribution

In this work, we investigate strategyproof mechanisms for the AS-GGASP with good welfare guarantee. In particular, we evaluate the performance of our mechanisms in terms of their approximation with respect to the maximum utilitarian social welfare. We develop our analysis by taking into account the possible values of the preferences among the activities and of the individual weights between agents. Namely, they can be either non-negative reals or unitary, that is 0 or 1. We highlight that all the presented mechanisms are anonymous.

D = deterministic, R = randomized, ∗ = copyable activities, † = anonymous mechanisms.

As a first result, we show that returning the optimum is not strategyproof, even if both preferences and weights are unitary. Thus, we focus on approximate mechanisms for nonnegative preferences. In this case, we show that no deterministic mechanism has a bounded approximation ratio for both non-negative (here, even for copyable activities) and unitary weights. Hence, we consider randomized mechanisms and design a simple k-approximate mechanism, where k is the number of activities. We also provide a 2- 2 k+1 and a 43 lower bound for non-negative and unitary weighs, respectively.

We then turn our attention to unitary preferences. We provide a k-approximate deterministic mechanism and a lower bound of Ω(√k ), holding for any strategyproof mechanism. When also weights are unitary, we show that a better deterministic mechanism exists whose approximation is 2.

Finally, we show refined almost tight bonds under reasonable assumptions. More precisely, when activities are copyable, we present a (2 - 1k )-approximate randomized mechanism. Furthermore, under unitary preferences, we show that no anonymous and deterministic mechanism has approximation < k, thus matching the above mentioned upper bound.

A summary of our results is given in Tables 1 and 2.

1.2 RelatedWork

In the past decade, considerable attention has been devoted to the GGASP [Darmann et al., 2018], as an interesting generalization of the well-known HGs [Dreze and Greenberg, 1980]. Most of the literature has focused on the subclasses of GGASP with anonymous preferences that allow a succinct representation. In particular, [Darmann et al., 2018] introduced the GASP and the approval-based version aGASP, while [Darmann, 2015] proposed the ordinal preferences oGASP. Other investigated classes of GASP are sGASP [Darmann et al., 2017], where there are a lower and an upper bound on the number of participants per activity, and gGASP [Igarashi et al., 2017b], where feasible coalitions must be connected components of a given interaction graph. In the above papers, individual and group deviations have been considered, providing several hardness results concerning the existence of stable solutions, plus positive results for particular cases. Some parameterized complexity studies in these subclasses have been developed in [Igarashi et al., 2017a; Ganian et al., 2018; Lee and Williams, 2017].

In the same spirit of ASHGs [Aziz et al., 2011], in [Bil`o et al., 2019] the AS-GGASP has been investigated, and results on the complexity of determining Nash stable outcomes and on the price of anarchy and stability have been given. Moreover, the NP-hardness of maximizing the utilitarian welfare has been proven, together with a (2 - 1/k)-approximation.

A nice introduction to GGASP and to the various subclasses can be found in [Andreas Darmann, 2016].

Some research in HGs and GGASP focused on the realistic setting in which agents' preferences are not known and the assignment of agents should be done so as to encourage their truthful reporting, as typically done in mechanism design. In particular, in [Wright and Vorobeychik, 2015] the authors provided a simple strategyproof mechanism for ASHGs with positive preferences that simply consist in grouping all agents together. A study of the properties of strategyproof core stable solutions for HGs has been provided also in [Rodr´ıguez´Alvarez, 2009]. A further step in this direction was made in [Flammini et al., 2021], where several strategyproof mechanisms for ASHG and other related classes of games have been presented under different assumptions on the agents' individual weights. The authors showed that no bounded strategyproof mechanism exists when weights can be arbitrary real numbers. This is the reason why, in this paper, we will restrict our attention to non-negative weights. Strategyproof mechanisms for Friends and Enemies games, a subclass of ASHGs, have also been considered. In this respect, while in [Dimitrov and Sung, 2004] the provided mechanisms return core stable outcomes, in [Flammini et al., 2022] the authors proposed solutions with a bounded approximation ratio with respect to the utilitarian social welfare. In [Darmann, 2019] the manipulability (not strategyproofness) of several reasonable rules (mechanisms), with the requirement of individual rationality, has been shown for three possible extensions of oGASP. Finally, in [Long, 2019] the authors provided strategyproof mechanisms for GASP with single-peaked preferences.

Strategyproof mechanisms have also been considered in several related settings, e.g. the house allocation problem [Bogomolnaia and Moulin, 2001; Adamczyk et al., 2014; Filos-Ratsikas et al., 2014], and the allocation of indivisible goods [Svensson, 1999]. Worth of mentioning is the machine scheduling setting. Here, some tasks must be split among machines and machines can declare their completion time for each task; the goal is to minimize the make-span. In [Nisan and Ronen, 2001] the authors provide an m-approximate mechanism, where m is the number of machines, together with a lower bound of 2. In [Ashlagi et al., 2012] this gap has only been closed for anonymous mechanisms: no anonymous mechanism can have an approximation better than m.

2 Model and Preliminaries

An AS-GGASP instance I = (G,A, p) is given by a directed weighted graph G = (V,E,w), where V is a set of n agents, A is a set of k activities, and p is a collection of agents' preferences. Namely, for each i ∈ V , pi : A → R expresses the value that agent i gives to each activity in A. Moreover, for each arc (i, j) ∈ E, the weight wi,j represents the appreciation that agent i has for agent j. We implicitly assume wi,j = 0 if (i, j) ̸∈ E. We denote by Wi(G) = ∑(i,j)∈E wi,j the overall evaluation that i ∈ V has for all the other agents and by W(G) = ∑i∈V Wi(G) the sum of all the arc weights of G.

Given an assignment or outcome z, zi is the activity of i in z, and δi(z) = ∑j∈V : zj=zi wi,j is the overall evaluation of i for the agents participating to zi. The utility of agent i in the assignment z is given by ui(z) = δi(z) + pi(zi).

In this work, we always assume both the preferences and weights to be non-negative. In particular, we consider preferences (resp. weights) which either take values in R≥0 or are unitary (i.e. in {0, 1}). To evaluate the performance of an assignment, we use the classical definition of utilitarian social welfare, given by SW(z) = ∑i∈V ui(z). Furthermore, we often express SW(z) as the sum xz + yz, where xz = ∑i∈V δi(z) and yz = ∑i∈V pi(zi). Given an instance I, the social optimum, denoted by opt(I), is the maximum utilitarian social welfare achievable by any assignment, and we denote by o(I) an assignment maximizing the utilitarian social welfare. When the instance is clear from the context, we refer to the social optimum and an optimal outcome simply as opt and o, respectively.

In our setting, for each agent i ∈ V , the preference function pi and the vector wi of all the weights wi,j are assumed to be private information of i, and must be declared by i before the assignment computation. In particular, each i communicates a pair di = (wd i , pdi ), where wd i and pdi are the individual weights vector and the preferences function, possibly different from her real pair of values vi = (wi, pi), and we let d = (d1, . . . , dn) be the collection of all such declarations.

A deterministic mechanismM is an algorithm that, for any declaration d, outputs an assignment zM(d) = M(d). Let d-i be the declarations of all the agents except i; a deterministic mechanism is said to be strategyproof (SP) if for any i ∈ V , d-i, di, and true vi, it satisfies ui(M(d-i, vi)) ≥ ui(M(d-i, di)). A randomized mechanism M maps every declaration d to a distribution ∆ over all the possible assignments. Thus, the expected utility of agent i is given by E [ui(M(d))] = Ez∼∆[ui(z)]. A randomized mechanism is said to be strategyproof (SP) if for any i ∈ V , d-i, di, and true vi, it satisfies E [ui(M(d-i, vi))] ≥ E [ui(M(d-i, di))].

A deterministic (resp. randomized) mechanism is said to be manipulable if it is not strategyproof. Further, a mechanism M is said to be anonymous if it does not rely on the agents identities. More formally, M is anonymous iff given any permutation π on the set of agents, M(i) = M(π(i)) for each i ∈ V , whereM(i) is the activity i is assigned to byM.

We evaluate the performance of M through the corresponding approximation ratio (AR) rM = supd opt(d) SW(M(d))

if M is deterministic, and rM = supd opt(d) E[SW(M(d))] if M is randomized. A mechanism is said to be bounded if there exists a bounded function f such that rM ≤ f(n, k). In what follows, we often identify agents' declaration d with the instance I(d) built according to d. For the sake of simplicity, we usually refer to I(d) as I.

So far, we assumed the activities to be non-copyable, i.e., for any assignment z and for each couple i, j ∈ V such that zi = zj, i ̸= j, we have that i and j participate together to the same activity, and thus contribute to each other's utility. If activities are copyable, instead, they may be performed by different subgroups of agents simultaneously; thus, each agent utility will count only for her own group members and not for all the other participants to the same activity. We observe that, in terms of social welfare, the copyability assumption does not lead to better solutions, since preferences and weights are assumed to be non-negative. However, it will be a useful feature to design efficient strategyproof mechanisms.

Social Optimumand Strategyproofness. We first observe that, since preferences and weights are non-negative, for k = 1 a trivial optimal strategyproof mechanism consists in assigning all agents to the single available activity. One might wonder whether a mechanism returning the optimum is also strategyproof when k ≥ 2. In [Bil`o et al., 2019], it is shown that for k ≥ 3 it is NP-hard to find the optimal allocation even if preferences and weights are unitary. We next show that, besides the fact that finding the optimum is not computationally tractable, a mechanism which returns an optimal solution is anyway not strategyproof for every k ≥ 2.

Proposition 1. A mechanism which returns the optimal allocation is not strategyproof even if preferences and weights are unitary and k = 2.

Proof. Let us consider instance I1 shown in Figure 1a, with unitary preferences and weights. In I1 we have the set of agents V = {1, 2, 3, 4, 5, 6, 7}, the set of activities A = {a1, a2}, preferences p1(a1) = p2(a1) = p4(a2) = p5(a2) = p6(a2) = p7(a2) = 1 and weights w1,3 = w2,3 = w3,4 = w4,5 = 1; any other value is 0. In I1 the optimum is achieved only by assigning 1, 2, 3 to a1 and 4, 5, 6, 7 to a2.

Let us now consider the I2 shown in Figure 1b, differing from I1 only for the declaration of agent 3, that is w3,5 = w3,6 = w3,7 = 1. In this case, in any optimal allocation, agent 3 is always assigned to activity a2 together with agent 4. For agent 3 in I1 it is preferable to get any optimal assignment for I2, rather than the one for I1. Hence, a mechanism returning the optimal assignment is manipulable.

Motivated by Proposition 1, we will focus on mechanisms returning good approximate solutions.

3 Non-Negative Preferences

In this section, we consider instances in which agents' preferences can be non-negative reals. We study arbitrary nonnegative and unitary weights in two separate subsections.

3.1 Non-NegativeWeights

In what follows, we show that every deterministic strategyproof mechanism has unbounded approximation ratio for any k ≥ 2. Thus, we turn our attention to randomized mechanisms whose approximation ratio is instead bounded. To this aim, we first provide the following necessary condition.

Lemma 1. Given a deterministic strategyproof mechanism M, for any instance I = (G,A, p) with non-negative preferences and non-negative weights, if rM is bounded then ui(zM(I)) ≥ 1n · (Wi(G) +maxa∈A pi(a)) holds ∀i ∈ V .

Proof. By contradiction, let us assume that there exists an instance I and an agent i ∈ V such that, in the returned assignment zM, ui(zM(I)) < 1n · (Wi(G) +maxa∈A pi(a)). Then, there must exist an activity a ∈ A such that a ̸= zM i and ui(zM) < pi(a) (case 1), or an agent j ∈ V \ {i} such that zM i ̸= zM j and ui(z)M < wi,j (case 2). Let us now consider a new instance I(M) where in case 1 (resp. case 2) agent i changes only the value she gives to the activity a (resp. to the agent j) and sets it to a suitably large positive number M. Since M is strategyproof, agent i will never be assigned to activity a (resp. to the same activity of j), otherwise agent i will achieve a better outcome in I by modifying it into I(M). Thus, as M increases, the ratio rM(I(M)) = opt(I(M)) SW(M(I(M))) ≥ M SW(M(I(M))) increases as well, contradicting the assumption that rM is bounded. Indeed, given any function f(n, k) for upper bounding rM, for suitably large M it is rM(I(M)) > f(n, k).

Exploiting the above property, we now show that no deterministic mechanism has bounded approximation ratio.

Theorem 1. No bounded deterministic strategyproof mechanism exists when preferences and weights are non-negative, even if k = 2 and activities are copyable.

Proof. Given any mechanismMwith bounded approximation ratio and a suitably large real number M ≫ 1, let us consider the instance I1 depicted in Fig. 2a. Since M is bounded, according to Lemma 1, it assigns (together) agent 1 and 2 to the same activity, let's say, activity a2.

Let us now consider instance I2 depicted in Fig. 2b, where α > 2. Due to Lemma 1, agent 2 must still be assigned byM to the same activity of 1. However, 1 and 2 cannot be assigned together to activity a1. In fact, if not, agent 1 in instance I1 can achieve a better outcome changing her preference for activity a1 and thus contradicting the strategyproofness of M. Therefore, in order to be strategyproof, M in I2 must assign both the agents to activity a2, violating Lemma 1 for agent 1.

In conclusion, a deterministic strategyproof mechanism achieving a bounded approximation ratio cannot exist.

(a) Instance I1

(b) Instance I2

Figure 2: LB for both deterministic and randomized mechanisms.

Since no bounded deterministic mechanism exists, we now present a simple randomized and anonymous mechanism.

MechanismM1. It selects uniformly at random one activity and then assigns all the agents to it.

Theorem 2. M1 is strategyproof and rM1 = k .

Proof. (SP) Since the assignment does not depend on the agents' declarations, the strategyproofness ofM1 follows.

(AR) Given an instance I, let z and o be the output of M1 and an optimal assignment for I, respectively.

Thus, E [xz] = W(G) ≥ xo and E [yz] is equal to 1k ∑i∈V ∑a∈A pi(a) ≥ 1k ∑i∈V pi(oi) = 1k · yo . Since xo ≤ E [xz] ≤ k · E [xz] and yo ≤ k · E [yz], we get rM = xo+yo E[xz+yz] ≤ k.

To show that this upper bound is tight, let us consider ˆ I = (G, A, p) with A = {a1, . . . , ak}, V = {1, . . . , k}, W(G) = 0, pi(aj) = 1 if and only if i = j, and pi(aj) = 0 otherwise. In this instance opt = k, while E [SW(M1(ˆ I))] = 1.

We next show a lower bound for any randomized strategyproof mechanism holding also in the copyable case.

Theorem 3. Given any randomized strategyproof mechanism M, under non-neg. preferences and weights, rM > 2- 2 k+1 .

Proof. Given V = {1, . . . , k, x} and A = {a1, . . . , ak}, let us consider the family of instances {Iα}α∈R+, where for any i, j ∈ {1, . . . , k}, pi(aj) = 1 iff i = j and wx,i = α for every i ∈ {1, . . . , k}. All the other values are set to 0.

Let ε be any strictly positive real number such that ε ≪ 1k , and let us consider the corresponding instance Iε. We observe that the optimal solution for Iε achieves a social welfare of opt(Iε) = k + ε, and it is obtained by assigning agent i to activity ai and agent x to any activity.

Given any randomized strategyproof mechanism M, we denote by c(k) = rM its approximation ratio. Let pm be the probability that agent x is assigned to an activity together with m ∈ {0, 1, . . . , k} other agents. Then, the expected utility of x in instance Iε is E [ux(M(Iε))] = ε · ∑km=0 m· pm . Moreover, it is possible to give a trivial upper bound to the expected social welfare assuming that: (a) if an agent i is not with x, then it is assigned to the activity she evaluates 1, and (b) one agent assigned together with x evaluates 1 the activity they belong to. Thus, we get E [SW(M(Iε))] ≤ ∑km=0 (ε · m+1+ (k -m)) · pm = k + 1 - (1 - ε) · ∑km=0 m · pm . We now use the strategyproofness assumption to give a lower bound on the expected number of agents assigned to the same activity of x. To this aim, we consider instance IM and define p′m as the probability that x is assigned to an activity together with other m ∈ {0, 1, . . . , k} agents. In this case we can express the expected utility of agent x as E [ux(M(IM))] = M · ∑km=0 m · p′m . Since M is strategyproof, ∑km=0 m · pm = ∑km=0 m · p′m must hold. Indeed, if ∑km=0 m · pm < ∑km=0 m · p′m, for agent x in instance Iε it would be possible to increase her expected utility by modifying Iε into IM, thus contradicting the strategyproofness of M. Similar arguments can be applied if we assume ∑km=0 m · pm > ∑km=0 m · p′m.

Let us assume M ≫ 1. In this case, opt(IM) = M · k + 1, as it can be checked by assigning all the agents to the same activity. Moreover, E [SW(M(IM))] ≤ M · ∑km=0 m· p′m + k. Since for any large enough M ≫ 1 it holds c(k) = rM ≥ kM+1 M·∑km=0 m·p′m+k M→∞ -→ k ∑km=0 m·p′m , we have that ∑km=0 m · p′m ≥ k c(k) . Applying the just provided lower bound to the expected social welfare for instance Iε, we get E [SW(M(Iε))] ≤ k + 1 - (1 - ε) · ∑km=0 m · pm ≤ k + 1 - (1 - ε) · k c(k) . Thus, we have k+ε k+1-(1-ε)· k c(k) ≤ c(k). For ε → 0, we finally obtain c(k) ≥ 2 · k k+1 = 2- 2 k+1 .

In Sec. 5, we show this LB is tight for copyable activities.

3.2 UnitaryWeights

Here we briefly discuss the unitary weights setting, i.e., wi,j ∈ {0, 1} for every i, j ∈ V . We refer to the full version of the paper for the technical details.

Unfortunately, a negative result holds also in this case.

Theorem 4. No deterministic strategyproof bounded mechanism exists for non-negative preferences, unitary weights, and non-copyable activities, even if k = 2.

Worth of mentioning is the main difference between Theorem 1 and 4. On the one hand, the lower bound showed for unitary weights seems to generalize the one for non-negative weights, on the other hand, the proof of Theorem 4 does not hold for the copyable case. Thus, finding a bounded deterministic mechanism for unitary weights and copyable activities remains an open question. Furthermore, Theorem 3 no longer hods, hence, we give a specific lower bound.

Theorem 5. For any randomized strategyproof mechanism M for non-neg. preferences and unitary weights, rM ≥ 43 .

4 Unitary Preferences

Given the previous negative results for arbitrary non-negative preferences, we now focus on unitary ones. Again, we distinguish between the cases of non-negative and unitary weights, and we show that in both cases it is possible to provide strategyproof mechanisms with bounded approximation ratio.

4.1 Non-NegativeWeights

Let us define by a∗ ∈ A the most preferred activity, i.e., a∗ = argmaxa∈A ∑i∈V pi(a), ties are broken lexicographically.

MechanismM2. It assigns all the agents to activity a∗ .

M2 is not strategyproof for non-negative preferences; this is not the case for unitary ones. Further, M2 is anonymous.

Theorem 6. M2 is strategyproof under unitary preferences and non-negative weights. Moreover, rM2 = k .

Proof. (SP) An agent is interested in manipulating only if she evaluates 0 the activity she is assigned to. However, not declaring her true preferences cannot improve the number of agents evaluating 1 the activities she likes.

Moreover, the bound is tight, it can be checked by considering the instance ˆ I described in the proof of Theorem 2.

We now provide a lower bound for any deterministic strategyproof mechanism. In Sec. 5 we will show a refined lower bound of k when mechanisms are anonymous.

Theorem 7. Given any deterministic and strategyproof mechanism M under unitary preferences and non-negative weights, rM ∈ Ω (√k).

Proof. Given any ε ≤ 1 k·2k , let us consider consider the instance following Iε = (G,A, p). The set of the activities is A = {a1, . . . , ak}, and ∀S ⊆ {1, . . . , k} = [k], S ̸= ∅, there is a corresponding agent ℓS. The set of the agents is V = [k] ∪ {ℓS|S ⊆ [k], S ̸= ∅}. Moreover, pi(ai) = 1 ∀ i ∈ [k], and wℓS,i = ε for each S ⊆ [k] and i ∈ S; all the other preferences and weights are set to 0.

Let M(Iε) be the assignment returned by mechanismM for instance Iε, and let {i1, . . . , im} with m ∈ [k] be the set of the agents assigned to the activity they evaluate 1 in M(Iε). Then, SW(M(Iε)) ≤ m+ c · ε for some c ≥ 0, while opt(Iε) ≥ k, thus implying rM ≥ k m+c·ε ε→0 -→ km .

Let us now consider S = {i1, . . . , im} and the corresponding agent ℓS, that must be assigned to only one activity and thus with only one of the agents in S. Such an agent may try to manipulate the outcome by changing the instance Iε into IS(M), where wℓS,i = M for each i ∈ S and all other preferences and weights are the same of Iε, with M suitably large. However, sinceMis strategyproof, this cannot lead to a better outcome for ℓS. Therefore, also in this instance ℓS cannot be assigned to an activity together with more than one agent in S. This means that SW(M(IS(M))) ≤ M + k + 1, while M→∞ -→ m.

To conclude, both r ≥ km and r ≥ m must hold. Minimizing the max of the two with respect to m, we get r ≥ √k.

4.2 UnitaryWeights

We now consider unitary preferences and weights. In what follows, we show that a mechanism better than M2 exists. Observe, in this case, G can be seen as a directed unweighted graph; this allows us to define CG as the set of maximal weakly connected components of G.

MechanismM3. It fixes a distinguished activity a ∈ A; for each C ∈ CG, if there exists ˆa ∈ A such that pi(ˆa) = 1 ∀i ∈ C, it assigns all the agents in C to ˆa, while it assigns them to a, otherwise.

Theorem 8. M3 is strategyproof under unitary preferences and weights, and rM3 = 2.

Proof. (SP) An agent i that truthfully reports her values is assigned with all the agents for which she has weight 1, thus, is not convenient for her misreporting her preferences among the other agents. If she lies to get an activity she values 1, she necessarily loses at least one of her neighbors, thus falling into an assignment not providing her a better utility.

(AR) We consider the SW of each component C ∈ CG separately. If there exists ˆa ∈ A such that pi(ˆa) = 1 ∀i ∈ C, then the SW of C is the maximum possible one. If agents in C do not have a common preferred activity, their SW is at least W(C), while the SW that C can achieve in any allocation is at most W(C) + |C| - 1 ≤ 2W(C). In fact, either they are assigned to a same activity, for which at least one of them has preference 0, or they are split among different activities, loosing at least 1 in terms of global weight.

Also in this case, M3 is anonymous. We also recall, any strategyproof mechanism M has rM > 1 by Proposition 1.

5 Improved Bounds

So far, we provided upper and lower bounds for strategyproof mechanisms under specific preferences and weights assumptions. In this section, we discuss meaningful cases in which such bounds become tight.

5.1 Copyable Activities

In this setting, we show that a mechanism better than M1 exists if activities are copyable.

MechanismM4. It selects z1 with probability k 2k-1 and z2 otherwise, where z1 is the outcome where all the agents are assigned to the same activity selected uniformly at random, and z2 is the outcome where each agent is assigned alone to one of the activities she prefers most.

Theorem 9. M4 is strategyproof, if activities are copyable, and preferences and weights are non-negative. Moreover, rM4 = 2 - 1k .

Proof. (SP) Observe, M4 outputs either z1 or z2 independently from the agents' declarations. Moreover, both z1 and z2 are strategyproof, hence, M4 is strategyproof as well.

(AR) Given an instance I, let z be the outcome returned by M4 and o be the optimal solution. Then, E [SW(z)] = k 2k-1 · E [SW(z1)] + k-1 2k-1 · SW(z2). Moreover, xo + 1k · yo ≤ E [SW(z1)] and yo ≤ SW(z2). In conclusion, opt ≤ E [SW(z1)] + k-1 k · SW(z2) = (2- 1k ) · E [SW(z)] . Such a bound is also tight, as it can be easily checked considering the instance ˆ I in the proof of Theorem 2.

By Theorem 3 we have that M4 is asymptotically optimal.

5.2 Anonymous Mechanisms

The main result of this subsection is given by the following:

Theorem 10. Under unitary preferences and non-negative weights, no anonymous strategyproof mechanism M can achieve an approximation ratio rM < k.

Observe that Mechanism M2 makes this bound tight.

To prove Theorem 10, we need the instance I ∗ described in the following. Let A = {a1, . . . , ak} be the set of activities, V = {1, . . . , k +1} be the set of agents, and ε be a small enough positive number. The agents preferences and weights are defined as follows: 1) pi(ai) = 1 for i = 1, . . . , k, 2) wi(j) = ε for i, j ∈ {1, . . . , k} and i ̸= j, and 3) wk+1(i) = ε for each i ∈ {1, . . . , k}.

All the other preferences and weights are set to 0.

Let M be any anonymous and strategyproof mechanism and z = M(I ∗ ) be the outcome for instance I ∗ . We define the mapping f : A → A, such that, for each i ∈ {1, . . . , k}, f(ai) = aj if and only if zi = aj. Notice that f depends on the considered mechanismM, for simplicity we omit it in the notation. Let us consider Im(f) = {f(a)|a ∈ A} and F ix(f ) = {a ∈ A|f (a) = a}.

We now present two useful lemmas, whose proofs can be found in the full version of the paper.

Lemma 2. Given any anonymous and strategyproof mechanismM, Im(f) = Fix(f) holds.

Lemma 3. Given any anonymous and strategyproof mechanismM , if k is prime number, either Fix(f) = A or there exists an activity a ∈ A such that F ix(f ) = {a}.

Proof of Theorem 10. Let us assume k to be a prime number. If Fix(f) = {a}, the claim follows as the opt in I ∗ is > k. If Fix(f) = A, every agent in {1, . . . , k} is assigned to her preferred activity, and thus agent k +1 can be assigned to an activity with only one other agent. In this case, let us consider the instance I ∗M where agent k +1 changes her weights from ε to M. Because of strategyproofness, no matter of how large M is, the mechanism will assign k + 1 to an activity together with only one other agent, otherwise she would modify I ∗ into I ∗M . In conclusion, for a sufficiently large M the optimum in I ∗M is obtained by assigning all the agents to the same activity achieving a social welfare of at least k · M + 1, while the best possible social welfare that the mechanism can achieve is at most k +M. Hence, the approximation ratio is at least k·M+1 k+M ; for M →∞ the claim holds.

6 Conclusion and FutureWork

In this work we investigated approximate strategyproof mechanisms for the AS-GGASP.

As for HGs and machine scheduling, there are relatively large gaps between some lower and upper bounds we provided. We circumvented this problem under some specific assumptions. Nonetheless, reducing gaps in the AS-GGASP, as well as in other related settings, remains a fundamental open question. Here, the crucial problem is to understand whether better, but not anonymous, mechanisms can be attained or if there are unexploited techniques to achieve improved bounds.

Another problem we left open is the existence of a bounded deterministic mechanism for copyable activities under nonnegative preferences and unitary weights.

Finally, we believe that our approach could be applied other relevant classes of the GGASP.

Acknowledgments

Giovanna Varricchio was supported by DFG grant Ho 3831/5-1.