Giovanna Varricchio

Maria Fomenko, Giovanna Varricchio

In this work, we study the additively separable Group Activity Selection Problem (AS-GASP) in an imperfect information setting, where agents have private preferences over activities and weights over other agents. Our goal is to design mechanisms that assign agents to activities based on their declared preferences and weights, with the objective of maximizing social welfare while ensuring truthful reporting. We, therefore, focus on the notion of non-obvious manipulability (NOM), a form of resilience to manipulation. We first investigate the relationship between NOM and social welfare optimality. In this regard, our main result shows that, when preferences and weights are arbitrary or non-negative, any optimal mechanism is non-obviously manipulable. In contrast, when either preferences or weights are binary, we show that optimality and NOM may be incompatible. We then turn to computational aspects. While it is known that computing an optimal outcome for the AS-GASP is NP-hard even in restricted settings, we establish a strong inapproximability result showing that no polynomial-time algorithm can guarantee a bounded approximation ratio when preferences and weights may take arbitrary values. In turn, when preferences are non-negative, we show that a bounded approximation is possible, and we present two asymptotically optimal approximation mechanisms that are also guaranteed to satisfy NOM.

Simone Fioravanti, Michele Flammini, Bojana Kodric et al.

We study PAC learnability and PAC stabilizability of Hedonic Games (HGs), i.e., efficiently inferring preferences or core-stable partitions from samples. We first expand the known learnability/stabilizability landscape for some of the most prominent HGs classes, providing results for Friends and Enemies Games, Bottom Responsive, and Anonymous HGs. Then, having a broader view in mind, we attempt to shed light on the structural properties leading to learnability/stabilizability, or lack thereof, for specific HGs classes. Along this path, we focus on the fully expressive Hedonic Coalition Nets representation of HGs. We identify two sets of conditions that lead to efficient learnability, and which encompass all of the known positive learnability results. On the side of stability, we reveal that, while the freedom of choosing an ad hoc adversarial distribution is the most obvious hurdle to achieving PAC stability, it is not the only one. First, we show a distribution independent necessary condition for PAC stability. Then, we focus on $\W$-games, where players have individual preferences over other players and evaluate coalitions based on the least preferred member. We prove that these games are PAC stabilizable under the class of bounded distributions, which assign positive probability mass to all coalitions. Finally, we discuss why such a result is not easily extendable to other HGs classes even in this promising scenario. Namely, we establish a purely computational property necessary for achieving PAC stability.

Simone Fioravanti, Michele Flammini, Bojana Kodric et al.

Hedonic Games (HGs) are a classical framework modeling coalition formation of strategic agents guided by their individual preferences. According to these preferences, it is desirable that a coalition structure (i.e. a partition of agents into coalitions) satisfies some form of stability. The most well-known and natural of such notions is arguably core-stability. Informally, a partition is core-stable if no subset of agents would like to deviate by regrouping in a so-called core-blocking coalition. Unfortunately, core-stable partitions seldom exist and even when they do, it is often computationally intractable to find one. To circumvent these problems, we propose the notion of $\varepsilon$-fractional core-stability, where at most an $\varepsilon$-fraction of all possible coalitions is allowed to core-block. It turns out that such a relaxation may guarantee both existence and polynomial-time computation. Specifically, we design efficient algorithms returning an $\varepsilon$-fractional core-stable partition, with $\varepsilon$ exponentially decreasing in the number of agents, for two fundamental classes of HGs: Simple Fractional and Anonymous. From a probabilistic point of view, being the definition of $\varepsilon$-fractional core equivalent to requiring that uniformly sampled coalitions core-block with probability lower than $\varepsilon$, we further extend the definition to handle more complex sampling distributions. Along this line, when valuations have to be learned from samples in a PAC-learning fashion, we give positive and negative results on which distributions allow the efficient computation of outcomes that are $\varepsilon$-fractional core-stable with arbitrarily high confidence.