Author name cluster

Giovanna Varricchio

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers

1 author row

AAMAS Conference 2026 Conference Paper

Maximizing the Egalitarian Welfare in Friends and Enemies Games

Edith Elkind
Michele Flammini
Giovanna Varricchio

We consider the complexity of maximizing egalitarian welfare in Friends and Enemies Games—a subclass of hedonic games in which every agent partitions other agents into friends and enemies. We investigate two classic scenarios proposed in the literature, namely, Friends Appreciation (FA) and Enemies Aversion (EA): in the former, each agent primarily cares about the number of friends in her coalition, breaking ties based on the number of enemies, while in the latter, the opposite is true. For EA, we show that our objective is hard to approximate within O(n1−ϵ), for any fixed ϵ > 0, and provide a polynomial-time (n − 1)-approximation. For FA, we obtain an NP-hardness result and a polynomial-time approximation algorithm. Our algorithm achieves a ratio of 2 − Θ(1 n ) when every agent has at least two friends; however, if some agent has at most one friend, its approximation ratio deteriorates to n/2. We recover the 2−Θ(1 n ) approximation ratio for two important variants: when randomization is allowed and when the friendship relationship is symmetric. Additionally, for both EA and FA we identify special cases where the optimal egalitarian partition can be computed in polynomial time.

PDF

AAAI Conference 2025 Conference Paper

Fair Division with Social Impact

Michele Flammini
Gianluigi Greco
Giovanna Varricchio

In this paper, we consider the problem of fair division of indivisible goods, where the allocation of goods impacts society. Specifically, we introduce a second valuation function for each agent, which determines the social impact of allocating a good to the agent. Such impact is considered desirable for the society -- the higher, the better. Our goal is to understand how to allocate goods fairly from the agents' perspective while maintaining society as happy as possible. To this end, we measure the impact on society using the utilitarian social welfare, and provide both possibility and impossibility results. Our findings reveal that achieving good approximations, better than linear in the number of agents, is not possible while ensuring fairness to the agents. These impossibility results can be attributed to the fact that agents are completely unconscious of their social impact. Consequently, we explore scenarios where agents are socially aware, by introducing related fairness notions, and demonstrate that an appropriate definition of fairness is compatible with the social objective.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Non-Obvious Manipulability in Additively Separable and Fractional Hedonic Games

Diodato Ferraioli
Giovanna Varricchio

In this work, we consider the design of Non-Obviously Manipulable (NOM) mechanisms, mechanisms that bounded rational agents may fail to recognize as manipulable, for two relevant classes of succinctly representable Hedonic Games: Additively Separable and Fractional Hedonic Games. In these classes, agents have cardinal scores towards other agents, and their preferences over coalitions are determined by aggregating such scores. This aggregation results in a utility function for each agent, which enables the evaluation of outcomes via the utilitarian social welfare. We first prove that, when scores can be arbitrary, every optimal mechanism is NOM; moreover, when scores are limited in a continuous interval, an optimal mechanism that is NOM exists. Given the hardness of computing optimal outcomes in these settings, we turn our attention to efficient and NOM mechanisms. To this aim, we first prove a characterization of NOM mechanisms that simplifies the class of mechanisms of interest. Then, we design a NOM mechanism returning approximations that asymptotically match the best-known approximation achievable in polynomial time. Finally, we focus on discrete scores, where the compatibility of NOM with optimality depends on the specific values. Therefore, we initiate a systematic analysis to identify which discrete values support this compatibility and which do not.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Non-obvious Manipulability in Hedonic Games with Friends Appreciation Preferences

Michele Flammini
Maria Fomenko
Giovanna Varricchio

In this paper, we study non-obvious manipulability (NOM), a relaxed form of strategyproofness, in the context of Hedonic Games (HGs) with Friends Appreciation (FA) preferences. In HGs, the aim is to partition agents into coalitions according to their preferences which solely depend on the coalition they are assigned to. Under FA preferences, agents consider any other agent either a friend or an enemy, preferring coalitions with more friends and, in case of ties, the ones with fewer enemies. Our goal is to design mechanisms that prevent manipulations while optimizing social welfare. Prior research established that computing a welfare maximizing (optimum) partition for FA preferences is not strategyproof, and the best-known approximation to the optimum subject to strategyproofness is linear in the number of agents. In this work, we explore NOM to improve approximation results. We first prove the existence of a NOM mechanism that always outputs the optimum; however, we also demonstrate that the computation of an optimal partition is NP-hard. To address this complexity, we focus on approximation mechanisms and propose a NOM mechanism guaranteeing a (4 + 𝑜(1))-approximation in polynomial time. Finally, we briefly discuss NOM in the case of Enemies Aversion (EA) preferences, the counterpart of FA, where agents give priority to coalitions with fewer enemies and show that no mechanism computing the optimum can be NOM.

PDF

JAIR Journal 2024 Journal Article

Best of Both Worlds: Agents with Entitlements

Martin Hoefer
Marco Schmalhofer
Giovanna Varricchio

Fair division of indivisible goods is a central challenge in artificial intelligence. For many prominent fairness criteria including envy-freeness (EF) or proportionality (PROP), no allocations satisfying these criteria might exist. Two popular remedies to this problem are randomization or relaxation of fairness concepts. A timely research direction is to combine the advantages of both, commonly referred to as Best of Both Worlds (BoBW). We consider fair division with entitlements, which allows to adjust notions of fairness to heterogeneous priorities among agents. This is an important generalization to standard fair division models and is not well-understood in terms of BoBW results. Our main result is a lottery for additive valuations and different entitlements that is ex-ante weighted envy-free (WEF), as well as ex-post weighted proportional up to one good (WPROP1) and weighted transfer envy-free up to one good (WEF(1, 1)). We show that this result is tight – ex-ante WEF is incompatible with any stronger ex-post WEF relaxation. In addition, we extend BoBW results on group fairness to entitlements and explore generalizations of our results to instances with more expressive valuation functions.

PDF Details DOI

NeurIPS Conference 2023 Conference Paper

$\varepsilon$-fractional core stability in Hedonic Games.

Simone Fioravanti
Michele Flammini
Bojana Kodric
Giovanna Varricchio

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.

PDF Details

AAMAS Conference 2023 Conference Paper

Best of Both Worlds: Agents with Entitlements

Martin Hoefer
Marco Schmalhofer
Giovanna Varricchio

Fair division of indivisible goods is a central challenge in artificial intelligence. For many prominent fairness criteria including envyfreeness (EF) or proportionality (PROP), no allocations satisfying these criteria might exist. Two popular remedies to this problem are randomization or relaxation of fairness concepts. A timely research direction is to combine the advantages of both, commonly referred to as Best of Both Worlds (BoBW). We consider fair division with entitlements, which allows to adjust notions of fairness to heterogeneous priorities among agents. This is an important generalization to standard fair division models and is not well-understood in terms of BoBW results. Our main result is a lottery for additive valuations and different entitlements that is ex-ante weighted envy-free (WEF), as well as ex-post weighted proportional up to one good (WPROP1) and weighted transfer envyfree up to one good (WEF(1, 1)). It can be computed in strongly polynomial time. We show that this result is tight – ex-ante WEF is incompatible with any stronger ex-post WEF relaxation. In addition, we extend BoBW results on group fairness to entitlements and explore generalizations of our results to instances with more expressive valuation functions.

PDF

IJCAI Conference 2023 Conference Paper

New Fairness Concepts for Allocating Indivisible Items

Ioannis Caragiannis
Jugal Garg
Nidhi Rathi
Eklavya Sharma
Giovanna Varricchio

For the fundamental problem of fairly dividing a set of indivisible items among agents, envy-freeness up to any item (EFX) and maximin fairness (MMS) are arguably the most compelling fairness concepts proposed till now. Unfortunately, despite significant efforts over the past few years, whether EFX allocations always exist is still an enigmatic open problem, let alone their efficient computation. Furthermore, today we know that MMS allocations are not always guaranteed to exist. These facts weaken the usefulness of both EFX and MMS, albeit their appealing conceptual characteristics. We propose two alternative fairness concepts—called epistemic EFX (EEFX) and minimum EFX value fairness (MXS)---inspired by EFX and MMS. For both, we explore their relationships to well-studied fairness notions and, more importantly, prove that EEFX and MXS allocations always exist and can be computed efficiently for additive valuations. Our results justify that the new fairness concepts are excellent alternatives to EFX and MMS.

PDF Details DOI

AAAI Conference 2023 Conference Paper

PAC Learning and Stabilizing Hedonic Games: Towards a Unifying Approach.

Simone Fioravanti
Michele Flammini
Bojana Kodric
Giovanna Varricchio

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.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Approximate Strategyproof Mechanisms for the Additively Separable Group Activity Selection Problem

Michele Flammini
Giovanna Varricchio

We investigate strategyproof mechanisms in the Group Activity Selection Problem with the additively separable property. Namely, agents have distinct preferences for each activity and individual weights for the other agents. We evaluate our mechanisms in terms of their approximation ratio with respect to the maximum utilitarian social welfare. We first show that, for arbitrary non-negative preferences, no deterministic mechanism can achieve a bounded approximation ratio. Thus, we provide a randomized k-approximate mechanism, where k is the number of activities, and a corresponding 2-2/(k+1) lower bound. Furthermore, we propose a tight (2 - 1/k)-approximate randomized mechanism when activities are copyable. We then turn our attention to instances where preferences can only be unitary, that is 0 or 1. In this case, we provide a k-approximate deterministic mechanism, which we show to be the best possible one within the class of strategyproof and anonymous mechanisms. We also provide a general lower bound of Ω({\sqrt{k}) when anonymity is no longer a constraint. Finally, we focus on unitary preferences and weights, and prove that, while any mechanism returning the optimum is not strategyproof, there exists a 2-approximate deterministic mechanism.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Maximizing Nash Social Welfare in 2-Value Instances

Hannaneh Akrami
Bhaskar Ray Chaudhury
Martin Hoefer
Kurt Mehlhorn
Marco Schmalhofer
Golnoosh Shahkarami
Giovanna Varricchio
Quentin Vermande

We consider the problem of maximizing the Nash social welfare when allocating a set G of indivisible goods to a set N of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent i ∈ N for every good j ∈ G is vij ∈ {p, q}, for p, q ∈ N, p ≤ q. In this work, we design an algorithm to compute an optimal allocation in polynomial time if p divides q, i. e. , when p = 1 and q ∈ N after appropriate scaling. The problem is NP-hard whenever p and q are coprime and p ≥ 3. In terms of approximation, we present positive and negative results for general p and q. We show that our algorithm obtains an approximation ratio of at most 1. 0345. Moreover, we prove that the problem is APX-hard, with a lower bound of 1. 000015 achieved at p/q = 4/5.

PDF Details

AIJ Journal 2022 Journal Article

Strategyproof mechanisms for Friends and Enemies Games

Michele Flammini
Bojana Kodric
Giovanna Varricchio

We investigate strategyproof mechanisms for Friends and Enemies Games, a subclass of Hedonic Games in which every agent classifies any other one as a friend or as an enemy. In this setting, we consider the two classical scenarios proposed in the literature, called Friends Appreciation ( FA ) and Enemies Aversion ( EA ). Roughly speaking, in the former each agent gives priority to the number of friends in her coalition, while in the latter to the number of enemies. We focus on the objective of maximizing the sum of the utilities of the agents and provide strategyproof mechanisms for both settings. More precisely, for FA we first present a deterministic n-approximation mechanism, n being the number of agents, and then show that a much better approximation can be achieved by resorting to randomization. Namely, we provide a randomized mechanism whose expected approximation ratio is 4, and arbitrarily close to 4 with high probability. For EA, we give a simple ( 1 + 2 ) n -approximation mechanism, and show that its performance is asymptotically tight by proving that it is NP-hard to approximate the optimal solution within O ( n 1 − ε ) for any fixed ε > 0. We also show that, if computational efficiency is not a concern, it is possible to achieve a ( 1 + 2 ) -approximation by means of a deterministic strategyproof mechanism with exponential runtime. Finally, we show how to extend our results in the presence of neutrals, i. e. , when agents can also be indifferent about other agents.

Details DOI

AAAI Conference 2020 Conference Paper

Strategyproof Mechanisms for Friends and Enemies Games

Michele Flammini
Bojana Kodric
Giovanna Varricchio

We investigate strategyproof mechanisms for Friends and Enemies Games, a subclass of Hedonic Games in which every agent classiﬁes any other one as a friend or as an enemy. In this setting, we consider the two classical scenarios proposed in the literature, called Friends Appreciation (FA) and Enemies Aversion (EA). Roughly speaking, in the former each agent gives priority to the number of friends in her coalition, while in the latter to the number of enemies. We provide strategyproof mechanisms for both settings. More precisely, for FA we ﬁrst present a deterministic napproximation mechanism, and then show that a much better result can be accomplished by resorting to randomization. Namely, we provide a randomized mechanism whose expected approximation ratio is 4, and arbitrarily close to 4 with high probability. For EA, we give a simple (1 + √ 2)napproximation mechanism, and show that its performance is asymptotically tight by proving that it is NP-hard to approximate the optimal solution within O(n1−ε ) for any ﬁxed ε > 0. Finally, we show how to extend our results in the presence of neutrals, i. e. , when agents can also be indifferent about other agents, and we discuss anonymity.

PDF Details