Hedonic Games and the Group Activity Selection Problem are two well-established models to describe the coalition formation of strategic agents. While most of the literature has been focusing on the existence and computation of stable outcomes, under the demanding assumption of complete knowledge of agents' preferences, very little has been made on the elicitation of true preferences.
CEUR ceur-ws.org
In many real-world scenarios, individuals prefer to perform tasks or activities by gathering into groups rather than being on their own. Simply think about researchers or employees working on diferent projects, politicians forming parties, people attending social events, and so forth. The increasing interest in economic, political, and social contexts in which individuals attempt common goals by splitting into groups led to the definition of Coalition Formation Games.
Coalition Formation Games model multi-agent systems where selfish agents form coalitions and have preferences over the possible outcomes of the game. More specifically, an outcome of a Coalition Formation Game is a partition of the agents into disjoint coalitions, and agents express their satisfaction with an outcome through preference relations. When agents’ preferences only depend on the coalition they belong to, and not on how the other agents aggregate, we talk about Hedonic Games (HGs), introduced by Dreze and Greenberg in [2]. Hedonic Games have been widely studied [3] and, according to the properties of agents’ preferences or other possible constraints, numerous classes have been defined.
IPS-RCRA-SPIRIT 2023: Italian Workshop on Planning and Scheduling, RCRA Workshop on Experimental evaluation of algorithms for solving problems with combinatorial explosion, and SPIRIT Workshop on Strategies, Prediction, Interaction, https://sites.google.com/view/giovanna-varricchio/ (G. Varricchio)
© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings
While on the one hand, Hedonic Games ofer a model sophisticated enough to describe a large variety of settings, on the other hand, they are not able to capture the satisfaction that agents have for the task they are eventually supposed to perform together. To this aim, the Group Activity Selection Problem (GASP), a proper generalization of the Hedonic Games, was introduced in [4]. Here, a set of possible tasks (or activities) is available, and the agents in a coalition have to perform a common task, one for each coalition. Thus, agents’ preferences are based on both the coalition they belong to and the activity they are supposed to perform.
In the Hedonic Games and Group Activity Selection Problem literature, diferent approaches have been considered, that can be broadly attributed to one of the two following research scenarios: i) the understanding of which kind of outcomes the selfish behavior of the agents leads to or ii) the elicitation of the agents’ real preferences while maintaining good properties for the designed outcome of the game.
Regarding the first research direction, agents’ preferences are known in advance and one of the main goals is to understand the outcomes that may be reached by the agents, both from an existential and an algorithmic perspective. To this aim, several stability concepts have been defined and studied which are based either on individual [ 5, 6, 7, 8, 9] or group deviations [10, 11, 12, 7, 13, 14].
In addition, when agents’ preferences are expressed by utilities, it is possible to measure the quality of stable outcomes by comparing their social welfare to the optimum (the maximum achievable one) [15, 16, 17, 18].
Regarding the second research direction, agents’ preferences are private information and must be communicated to a designer who splits agents accordingly. Being agents selfish, they may misreport their preferences so as to maximize their satisfaction with the final outcome of the game. Then the designer, solely based on the reported preferences, must compute an outcome of the game in order to induce, without any monetary request, a truthful behavior of the agents while satisfying good properties, for instance, stability or a good approximation of the optimum. This is known as the Mechanism Design without Money framework. In particular, in this setting, the outcome of the game is computed by an algorithm commonly called mechanism; a mechanism is said to be a strategyproof if no agent has an incentive to misreport her private information.
We focus on strategyproof mechanisms guaranteeing a good approximation to the optimum in the context of HGs and the GASP. The paper is organized as follows: In Section 2, we give an overview of the state of the art. In Section 3, we point out the limits of the current literature and establish which are the key challenges in this area.
In this section, we give an overview of the literature on strategyproof mechanisms with good guarantees with respect to the optimum. We assume that agents’ preferences are expressed by means of utilities and that the utility of an agent for a given outcome can be univocally determined by the individual values given to the other agents and the activities. Such values are a private information of the agents and have to be communicated to the central authority so as to compute an outcome of the game. More formally, we assume that, given a set of agents and a set of activities , every agent has a weight for any other agent ∈ ⧵ { } and a preference for each activity ∈ 1. Hence, the utility an agent has for being a member of a specific group and participating in a certain activity can be computed according to the weights she has for her coalition members and the preference she has for the activity they are performing. We will describe specific classes that fit this definition in the subsequent paragraphs.
We evaluate the quality of an outcome by its utilitarian welfare, that is, the sum of agents’ utilities, and measure the performances of the provided strategyproof mechanisms by comparing the social welfare they achieve (deterministically or in expectation) to the optimal one. In principle, a strategyproof mechanism may have an unbounded approximation guarantee to the optimum; whenever a mechanism has a bounded approximation guarantee we simply call it a bounded mechanism.
In what follows, having a lower bound of value means no strategyproof mechanism can
achieve an approximation better than . In turn, we say we have an upper bound of value if
a strategyproof mechanism guaranteeing an -approximation exists. Moreover, whenever a
lower bound is > 1 means that any mechanism returning the optimum is not strategyproof.
Additively Separable Hedonic Games. In additively separable HGs (ASHGs) an agent
values a coalition , such that ∈ , by simply summing up the weights she has for each member,
that is, () = ∑∈⧵ { } . In [19, 20], the problem of achieving good approximate mechanisms
with respect to the maximum utilitarian welfare has been considered under several assumptions
on the weights , see Table 1. First of all, the authors showed that there is a dichotomy between
the cases where ∈ [
Fractional Hedonic Games. Similarly to ASHGs, in fractional HGs (FHGs), the utility an agent ∈ ⊆
derives in being included in the coalition is obtained by summing up the weights she has for the other participants and then normalizing by the coalition size; { } . The work [20] gives a complete picture of approximate strategyproof formally, () = ∑∈⧵
||
mechanisms for FHGs by making a case distinction between the possible values for the weights
and we showcase them in Table 2. Similarly to the ASHGs case, the freedom of choosing
both negative and positive weights in the interval [
[
For these two specific classes, the existence of strategyproof mechanisms outputting core or weak core stable solutions is well-established. However, these results are either ineficient or require exponential time to be executed. In [22], a complete picture of both positive and negative results on approximate strategyproof mechanisms is provided and we summarize their main results in Table 3. For FA preference profiles it is well-known that splitting the agents into maximal strongly connected components, in the directed graphs where agents are the nodes and directed edges represent friendship relationships, is strategyproof and core stable [23]; however, this mechanism is particularly ineficient in approximating the utilitarian welfare. In turn, [ 22] shows that splitting agents into maximal weakly connected components is still strategyproof and guarantees an approximation linear in the number of agents; however, such mechanism does not necessarily provide core stable outcomes. Furthermore, a 4-approximation is possible when relying on randomization. Concerning EA profiles, repeatedly extracting and creating a coalition with a maximum clique, in the undirected graph of mutual friendship, is strategyproof and provides a weak core stable outcome [23]; moreover, it gives a constant approximation w.r.t. the optimal utilitarian welfare [22]. Unfortunately, such a procedure is not computationally eficient. In turn, via a matching algorithm, it is possible to achieve a strategyproof mechanism having linear approximation in the number of agents. in HGs. L.B. and U.B. stand for lower and upper bound, respectively; denotes the number of agents.
the results obtained in [24] on approximate strategyproof mechanisms for the additively separable GASP (ASGASP). Here, the utility of an agent ∈ ⊆ for participating in an activity with the coalition is given by the sum of the weights for the other coalition members and the preference she has for the activity , that is, (, ) = + ∑∈⧵ { } . The provided results take into account the possible values of the preferences among the activities and of the individual weights between the agents. Considering the impossibility result for ASHGs when weights may be both positive and negative reals, we can conclude that no bounded strategyproof mechanism exists for the ASGASP as well. Therefore, the authors distinguished the analysis considering non-negative or binary values towards agents/activities. A complete picture of the results is given in Table 4.
In the case of non-negative preferences, it is possible to show that, even if ∈ {0, 1}, no deterministic mechanism can achieve a bounded approximation ratio. In turn, when relying on randomized mechanisms, a simple -approximate mechanism, where is the number of activities, exists. Such a result is indeed possible by selecting uniformly at random to which activity all agents will be assigned; this makes the mechanisms independent of the agents’ preferences for the activity and therefore no misreport can be successful. In fact, the main reason for the impossibility of a bounded deterministic mechanism is the freedom of agents in selecting high values for the most preferred activity. In contrast, when agents have limited expressiveness on their preferences over activities, bounded deterministic mechanisms are possible. Specifically, if agents’ preferences are boolean, a -approximate deterministic mechanism exists; however, it was only possible to show an Ω (√ ) lower bound. An interesting fact is that the -approximate mechanism is indeed tight when restricting the attention on anonymous mechanisms2. Finally, 2Anonymous means that the computation of the outcome does not depend on the agents’ identities. when the weights towards other agents are also binary, a 2-approximate deterministic, and therefore randomized, mechanism is attainable.
stand for lower and upper bounds respectively. Randomized mechanisms are denoted by ∗, results for anonymous mechanisms are denoted by †, and is the number of activities.
Boolean preferences: ∈ {0, 1}.
As we already mentioned, very little is known about mechanisms design for HGs and the GASP. Other than good approximation guarantees, strategyproof mechanisms or manipulability aspects, that is, non-strategyproofness of a certain allocation rule, are considered for example in [25, 26].
In this section, we draw a landscape of compelling future research directions in the sense of approximate strategyproof mechanisms. We anyway consider the goal of finding strategyproof mechanisms guaranteeing some stability notion clearly of interest.
We have seen there exists a number of settings where bounded strategyproof mechanisms are not possible. In these circumstances, strategyproofness turns out to be very demanding and it looks natural to question whether a more relaxed notion may lead to a bounded approximation. More specifically, one could allow the agents to misreport their private information up to some extent, e.g. the distance from their actual private information can be bounded by some constant or the number of misreported values is limited. On the other hand, the reason why bounded mechanisms are not possible in some contexts can be attributed to the fact that agents have too much freedom in their declarations. Since agents do not incur any penalty for arbitrarily raising their values, this allows them to manipulate not only optimal but also approximate solutions. Monetary transfers could disincentivize such kinds of manipulations and, therefore, considering mechanisms with payments is another way we may hope to circumvent impossibility results.
Although some of the provided mechanisms are bounded, the question if their guarantee is the best attainable in conjunction with strategyproofness remains open. In the case of the ASGASP, with binary preferences and arbitrary weights, a matching lower bound was possible only by assuming anonymity while, in general, the gap remains open. We suspect that anonymity is indeed not needed to show a lower bound of and that the provided mechanism is the best possible. Such a belief is driven by what happened in the study of strategyproof mechanisms for machine scheduling. 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 [27] the authors provide an -approximate mechanism, where is the number of machines, together with a lower bound of 2. Subsequently, this gap has been closed for anonymous mechanisms: no anonymous mechanism can have an approximation better than [28]. Only recently, the lower bound has been shown to be (without the anonymity condition) both with or without money [29]. It would be interesting therefore to understand if a similar result is possible for the ASGASP; moreover, it is also worth considering anonymous mechanisms in the context of HGs as a first step for tightening bounds. We finally want to highlight that while, on the one hand, the mechanisms have been designed to work in polynomial time (if not specified otherwise), on the other hand, the obtained lower bounds do not depend on the time complexity. Hence, it might be possible to establish whether the provided upper bounds are the best possible for poly-time mechanisms.
Considering new classes of games. Other than the aforementioned, there exist other HGs classes that are suitable for the study of approximate strategyproof mechanisms. For example, social distance [30] and distance hedonic [31] games are two generalizations of (simple) FHGs where agents lay in a social network and derive their utility according to their induced distance from the other agents in their coalition. In such games, agents can only hide their connections to other agents rather than provide the values they retain by being in a certain coalition. This intuitively suggests that the agents do not have much room for manipulation which makes attractive the idea of studying approximate strategyproof mechanisms in this setting. In the paper [32], strategyproof and approximately envy-free mechanisms for ASHGs with bounded coalition size are considered. Their main contribution is a mechanism that achieves good experimental performances. Approximate strategyproof mechanisms (w.r.t. the utilitarian social welfare) for HGs and the GASP with bounded coalition size are also worth considering.
All in all, the study of strategyproof mechanisms is clearly of interest in all those scenarios where strategic agents have to be split by a central authority into coalitions. So far, very little is known in the case of HGs and the GASP, and many questions are open.
This paper was supported by the PNRR MIUR project FAIR – Future AI Research (PE00000013) and the DFG, German Research Foundation, grant (Ho 3831/5-1).
The author is grateful to Michele Flammini and Simone Fioravanti for their helpful comments. Interaction, and Reasoning in Italy (IPS-RCRA-SPIRIT 2023), in: Proceedings of the Italian Workshop on Planning and Scheduling, RCRA Workshop on Experimental evaluation of algorithms for solving problems with combinatorial explosion, and SPIRIT Workshop on Strategies, Prediction, Interaction, and Reasoning in Italy (IPS-RCRA-SPIRIT 2023) co-located with 22th International Conference of the Italian Association for Artificial Intelligence (AI* IA 2023), 2023. [2] J. H. Dreze, J. Greenberg, Hedonic coalitions: Optimality and stability, Econometrica:
Journal of the Econometric Society (1980) 987–1003. [3] H. Aziz, R. Savani, Hedonic games, in: Handbook of Computational Social Choice.,
Handbook of Computational Social Choice. Cambridge University Press, 2016. [4] A. Darmann, E. Elkind, S. Kurz, J. Lang, J. Schauer, G. Woeginger, Group activity selection problem, in: Proceedings of the 8th International Conference on Web and Internet Economics (WINE), Springer, 2012, pp. 156–169. [5] F. Bloch, E. Diamantoudi, Noncooperative formation of coalitions in hedonic games, Int. J.
Game Theory 40 (2011) 263–280. [6] M. Feldman, L. Lewin-Eytan, J. Naor, Hedonic clustering games, TOPC 2 (2015) 4:1–4:48. [7] M. Gairing, R. Savani, Computing stable outcomes in symmetric additively separable hedonic games, Math. Oper. Res. 44 (2019) 1101–1121. [8] V. Bilò, A. Fanelli, M. Flammini, G. Monaco, L. Moscardelli, Optimality and nash stability in additively separable generalized group activity selection problems, in: Proceedings of the 28th International Joint Conference on Artificial Intelligence(IJCAI), 2019, pp. 102–108. [9] A. Darmann, Stable and pareto optimal group activity selection from ordinal preferences, volume 47, 2018, pp. 1183–1209. [10] A. Bogomolnaia, M. O. Jackson, et al., The stability of hedonic coalition structures, Games and Economic Behavior 38 (2002) 201–230. [11] S. Banerjee, H. Konishi, T. Sönmez, Core in a simple coalition formation game, Social
Choice & Welfare 18 (2001) 135–153. [12] E. Elkind, M. J. Wooldridge, Hedonic coalition nets, in: Proceedings of the 8th International
Conference of Autonomous Agents and Multi-Agent Systems (AAMAS), 2009, pp. 417–424. [13] A. Igarashi, E. Elkind, Hedonic games with graph-restricted communication, in: Proceedings of the 15th International Conference of Autonomous Agents and Multi-Agent Systems (AAMAS), ACM, 2016, pp. 242–250. [14] A. Darmann, E. Elkind, S. Kurz, J. Lang, J. Schauer, G. J. Woeginger, Group activity selection problem with approval preferences, Int. J. Game Theory 47 (2018) 767–796. [15] V. Bilò, A. Fanelli, M. Flammini, G. Monaco, L. Moscardelli, On the price of stability of fractional hedonic games, in: Proceedings of the 14th International Conference of Autonomous Agents and Multi-Agent Systems (AAMAS), ACM, 2015, pp. 1239–1247. [16] C. Kaklamanis, P. Kanellopoulos, D. Patouchas, On the price of stability of social distance games, in: Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT), volume 11059, 2018, pp. 125–136. [17] A. Balliu, M. Flammini, G. Melideo, D. Olivetti, Nash stability in social distance games, in:
Proceedings of the 31st Conference on Artificial Intelligence (AAAI), 2017, pp. 342–348. [18] M. Flammini, B. Kodric, M. Olsen, G. Varricchio, Distance hedonic games, in: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, Auckland, New Zealand, May 9-13, 2020, 2020, pp. 1846–1848. [19] M. Flammini, G. Monaco, Q. Zhang, Strategyproof mechanisms for additively separable hedonic games and fractional hedonic games, in: Proceedings of the 15th International Workshop on Approximation and Online Algorithms (WAOA), 2017, pp. 301–316. [20] M. Flammini, B. Kodric, G. Monaco, Q. Zhang, Strategyproof mechanisms for additively separable and fractional hedonic games, Journal of Artificial Intelligence Research 70 (2021) 1253–1279. [21] D. Dimitrov, P. Borm, R. Hendrickx, S. C. Sung, Simple priorities and core stability in hedonic games, Social Choice & Welfare 26 (2006) 421–433. [22] M. Flammini, B. Kodric, G. Varricchio, Strategyproof mechanisms for friends and enemies games, Artificial Intelligence 302 (2022) 103610. [23] D. Dimitrov, S. C. Sung, Enemies and friends in hedonic games: individual deviations, stability and manipulation, CentER Discussion Paper Series (2004). [24] M. Flammini, G. Varricchio, et al., Approximate strategyproof mechanisms for the additively separable group activity selection problem, in: Thirty-First International Joint Conference on Artificial Intelligence, 2022, pp. 300–306. [25] A. Darmann, Manipulability in a group activity selection problem, Social Choice & Welfare 52 (2019) 527–557. [26] N. Waxman, S. Kraus, N. Hazon, Manipulation of k-coalitional games on social networks, in: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, 2021, pp. 450–457. [27] N. Nisan, A. Ronen, Algorithmic mechanism design, Games and Economic behavior 35 (2001) 166–196. [28] I. Ashlagi, S. Dobzinski, R. Lavi, Optimal lower bounds for anonymous scheduling mechanisms, Mathematics of Operations Research 37 (2012) 244–258. [29] G. Christodoulou, E. Koutsoupias, A. Kovács, A proof of the nisan-ronen conjecture, in: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, pp. 672–685. [30] S. Brânzei, K. Larson, Social distance games, in: Proceedings of the 22nd International
Joint Conference on Artificial Intelligence(IJCAI), 2011, pp. 91–96. [31] M. Flammini, B. Kodric, M. Olsen, G. Varricchio, Distance hedonic games, in: International Conference on Current Trends in Theory and Practice of Informatics, Springer, 2021, pp. 159–174. [32] M. Wright, Y. Vorobeychik, Mechanism design for team formation, in: Proceedings of the 29th Conference on Artificial Intelligence (AAAI), 2015, pp. 1050–1056.