Arrow Research search

Author name cluster

Angelo Fanelli

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.

14 papers
1 author row

Possible papers

14

AAAI Conference 2025 Conference Paper

Individually Stable Dynamics in Coalition Formation over Graphs

  • Angelo Fanelli
  • Laurent Gourvès
  • Ayumi Igarashi
  • Luca Moscardelli

Coalition formation over graphs is a well studied class of games whose players are vertices and feasible coalitions must be connected subgraphs. In this setting, the existence and computation of equilibria, under various notions of stability, has attracted a lot of attention. However, the natural process by which players, starting from any feasible state, strive to reach an equilibrium after a series of unilateral improving deviations, has been less studied. We investigate the convergence of dynamics towards individually stable outcomes under the following perspective: what are the most general classes of preferences and graph topologies guaranteeing convergence? To this aim, on the one hand, we cover a hierarchy of preferences, ranging from the most general to a subcase of additively separable preferences, including individually rational and monotone cases. On the other hand, given that convergence may fail in graphs admitting a cycle even in our most restrictive preference class, we analyze acyclic graph topologies such as trees, paths, and stars.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Minimizing Rosenthal's Potential in Monotone Congestion Games

  • Vittorio Bilò
  • Angelo Fanelli
  • Laurent Gourvès
  • Christos Tsoufis
  • Cosimo Vinci

Congestion games are attractive because they can model many concrete situations where some competing entities interact through the use of some shared resources, and also because they always admit pure Nash equilibria which correspond to the local minima of a potential function. We explore the problem of computing a state of minimum potential in this setting. Using the maximum number of resources that a player can use at a time, and the possible symmetry in the players’ strategy spaces, we settle the complexity of the problem for instances having monotone (i. e. , either non-decreasing or non-increasing) latency functions on their resources. The picture, delineating polynomial and NP-hard cases, is complemented with tight approximation algorithms.

PDF

AIJ Journal 2025 Journal Article

Relaxed core stability in hedonic games

  • Angelo Fanelli
  • Gianpiero Monaco
  • Luca Moscardelli

The core is a well-known and fundamental notion of stability in games intended to model coalition formation such as hedonic games: an outcome is core stable if there exists no blocking coalition, i. e. , no set of agents that may profit by forming a coalition together. The fact that the cardinality of a blocking coalition, i. e. , the number of deviating agents that have to coordinate themselves, can be arbitrarily high, and the fact that agents may benefit only by a tiny amount from their deviation, while they could incur in a higher cost for deviating, suggest that the core is not able to suitably model practical scenarios in large and highly distributed multi-agent systems. For this reason, we consider relaxed core stable outcomes where the notion of permissible deviations is modified along two orthogonal directions: the former takes into account the size q of the deviating coalition, and the latter the amount of utility gain, in terms of a multiplicative factor k, for each member of the deviating coalition. These changes result in two different notions of stability, namely, the q-size core and k-improvement core. We consider fractional hedonic games, that is a well-known subclass of hedonic games for which core stable outcomes are not guaranteed to exist and it is computationally hard to decide non-emptiness of the core; we investigate these relaxed concepts of stability with respect to their existence, computability and performance in terms of price of anarchy and price of stability, by providing in many cases tight or almost tight bounds. Interestingly, the considered relaxed notions of core also possess the appealing property of recovering, in some notable cases, the convergence, the existence and the possibility of computing stable solutions in polynomial time.

Details DOI

IJCAI Conference 2021 Conference Paper

Relaxed Core Stability in Fractional Hedonic Games

  • Angelo Fanelli
  • Gianpiero Monaco
  • Luca Moscardelli

The core is a well-known and fundamental notion of stability in games intended to model coalition formation such as hedonic games. The fact that the number of deviating agents (that have to coordinate themselves) can be arbitrarily high, and the fact that agents may benefit only by a tiny amount from their deviation (while they could incur in a cost for deviating), suggest that the core is not able to suitably model many practical scenarios in large and highly distributed multi-agent systems. For this reason, we consider relaxed core stable outcomes where the notion of permissible deviations is modified along two orthogonal directions: the former takes into account the size of the deviating coalition, and the latter the amount of utility gain for each member of the deviating coalition. These changes result in two different notions of stability, namely, the q-size core and k-improvement core. We investigate these concepts of stability in fractional hedonic games, that is a well-known subclass of hedonic games for which core stable outcomes are not guaranteed to exist and it is computationally hard to decide nonemptiness of the core. Interestingly, the considered relaxed notions of core also possess the appealing property of recovering, in some notable cases, the convergence, the existence and the possibility of computing stable solutions in polynomial time.

PDF Details DOI

AIJ Journal 2020 Journal Article

Price of Pareto Optimality in hedonic games

  • Edith Elkind
  • Angelo Fanelli
  • Michele Flammini

The Price of Anarchy measures the welfare loss caused by selfish behavior: it is defined as the ratio of the social welfare in a socially optimal outcome and in a worst Nash equilibrium. Similar measures can be derived for other classes of stable outcomes. We observe that Pareto optimality can be seen as a notion of stability: an outcome is Pareto optimal if and only if it does not admit a deviation by the grand coalition that makes all players weakly better off and some players strictly better off. Motivated by this observation, we introduce the concept of Price of Pareto Optimality: this is an analogue of the Price of Anarchy, with the worst Nash equilibrium replaced with the worst Pareto optimal outcome. We then study this concept in the context of hedonic games, and provide lower and upper bounds on the Price of Pareto Optimality in three classes of hedonic games: additively separable hedonic games, fractional hedonic games, and modified fractional hedonic games.

Details DOI

AAAI Conference 2019 Conference Paper

Consensus in Opinion Formation Processes in Fully Evolving Environments

  • Vincenzo Auletta
  • Angelo Fanelli
  • Diodato Ferraioli

(Friedkin and Johnsen 1990) modeled opinion formation in social networks as a dynamic process which evolves in rounds: at each round each agent updates her expressed opinion to a weighted average of her innate belief and the opinions expressed in the previous round by her social neighbors. The stubbornness level of an agent represents the tendency of the agent to express an opinion close to her innate belief. Motivated by the observation that innate beliefs, stubbornness levels and even social relations can co-evolve together with the expressed opinions, we present a new model of opinion formation where the dynamics runs in a co-evolving environment. We assume that agents’ stubbornness and social relations can vary arbitrarily, while their innate beliefs slowly change as a function of the opinions they expressed in the past. We prove that, in our model, the opinion formation dynamics converges to a consensus if reasonable conditions on the structure of the social relationships and on how the personal beliefs can change are satisfied. Moreover, we discuss how this result applies in several simpler (but realistic) settings.

PDF Details

IJCAI Conference 2019 Conference Paper

Optimality and Nash Stability in Additive Separable Generalized Group Activity Selection Problems

  • Vittorio Bilò
  • Angelo Fanelli
  • Michele Flammini
  • Gianpiero Monaco
  • Luca Moscardelli

The generalized group activity selection problem (GGASP) consists in assigning agents to activities according to their preferences, which depend on both the activity and the set of its participants. We consider additively separable GGASPs, where every agent has a separate valuation for each activity as well as for any other agent, and her overall utility is given by the sum of the valuations she has for the selected activity and its participants. Depending on the nature of the agents' valuations, nine different variants of the problem arise. We completely characterize the complexity of computing a social optimum and provide approximation algorithms for the NP-hard cases. We also focus on Nash stable outcomes, for which we give some complexity results and a full picture of the related performance by providing tights bounds on both the price of anarchy and the price of stability.

PDF Details

JAIR Journal 2018 Journal Article

Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation

  • Vittorio Bilò
  • Angelo Fanelli
  • Michele Flammini
  • Gianpiero Monaco
  • Luca Moscardelli

We consider fractional hedonic games, a subclass of coalition formation games that can be succinctly modeled by means of a graph in which nodes represent agents and edge weights the degree of preference of the corresponding endpoints. The happiness or utility of an agent for being in a coalition is the average value she ascribes to its members. We adopt Nash stable outcomes as the target solution concept; that is we focus on states in which no agent can improve her utility by unilaterally changing her own group. We provide existence, efficiency and complexity results for games played on both general and specific graph topologies. As to the efficiency results, we mainly study the quality of the best Nash stable outcome and refer to the ratio between the social welfare of an optimal coalition structure and the one of such an equilibrium as to the price of stability. In this respect, we remark that a best Nash stable outcome has a natural meaning of stability, since it is the optimal solution among the ones which can be accepted by selfish agents. We provide upper and lower bounds on the price of stability for different topologies, both in case of weighted and unweighted edges. Beside the results for general graphs, we give refined bounds for various specific cases, such as triangle-free, bipartite graphs and tree graphs. For these families, we also show how to efficiently compute Nash stable outcomes with provable good social welfare.

PDF Details DOI

TCS Journal 2018 Journal Article

Opinion formation games with dynamic social influences

  • Vittorio Bilò
  • Angelo Fanelli
  • Luca Moscardelli

We investigate opinion formation games with dynamic social influences, where opinion formation and social relationships co-evolve in a cross-influencing manner. We show that these games always admit an ordinal potential, and so, pure Nash equilibria, and we design a polynomial time algorithm for computing the set of all pure Nash equilibria and the set of all social optima of a given game. We also derive non-tight upper and lower bounds on the price of anarchy and stability which only depend on the players' stubbornness, that is, on the scaling factor used to counterbalance the cost that a player incurs for disagreeing with the society and the cost she incurs for breaking away from her innate beliefs.

Details DOI

AAAI Conference 2016 Conference Paper

Price of Pareto Optimality in Hedonic Games

  • Edith Elkind
  • Angelo Fanelli
  • Michele Flammini

Price of Anarchy measures the welfare loss caused by selfish behavior: it is defined as the ratio of the social welfare in a socially optimal outcome and in a worst Nash equilibrium. A similar measure can be derived for other classes of stable outcomes. In this paper, we argue that Pareto optimality can be seen as a notion of stability, and introduce the concept of Price of Pareto Optimality: this is an analogue of the Price of Anarchy, where the maximum is computed over the class of Pareto optimal outcomes, i. e. , outcomes that do not permit a deviation by the grand coalition that makes all players weakly better off and some players strictly better off. As a case study, we focus on hedonic games, and provide lower and upper bounds of the Price of Pareto Optimality in three classes of hedonic games: additively separable hedonic games, fractional hedonic games, and modified fractional hedonic games; for fractional hedonic games on trees our bounds are tight.

PDF Details

TCS Journal 2016 Journal Article

The price of envy-freeness in machine scheduling

  • Vittorio Bilò
  • Angelo Fanelli
  • Michele Flammini
  • Gianpiero Monaco
  • Luca Moscardelli

We consider k-envy-free assignments for scheduling problems in which the completion time of each machine is not k times larger than the one she could achieve by getting the jobs of another machine, for a given factor k ≥ 1. We introduce and investigate the notion of price of k-envy-freeness, defined as the ratio between the makespan of the best k-envy-free assignment and that of an optimal allocation achievable without envy-freeness constraints. We provide exact or asymptotically tight bounds on the price of k-envy-freeness for all the basic scheduling models, that is unrelated, related and identical machines. Moreover, we show how to efficiently compute such allocations with a worsening multiplicative factor being at most the best approximation ratio for the minimum makespan problem guaranteed by a polynomial time algorithm for each specific model. Finally, we extend our results to the case of restricted assignments and to the objective of minimizing the sum of the completion times of all the machines.

Details DOI

TCS Journal 2015 Journal Article

The ring design game with fair cost allocation

  • Angelo Fanelli
  • Dariusz Leniowski
  • Gianpiero Monaco
  • Piotr Sankowski

In this paper we study the network design game when the underlying network is a ring. In a network design game we have a set of players, each of them aims at connecting nodes in a network by installing links and equally sharing the cost of the installation with other users. The ring design game is the special case in which the potential links of the network form a ring. It is well known that in a ring design game the price of anarchy may be as large as the number of players. Our aim is to show that, despite the worst case, the ring design game always possesses good equilibria. In particular, we prove that the price of stability of the ring design game is at most 3/2, and such bound is tight. Moreover, we observe that the worst Nash equilibrium cannot cost more than 2 times the optimum if the price of stability is strictly larger than 1. We believe that our results might be useful for the analysis of more involved topologies of graphs, e. g. , planar graphs.

Details DOI

IJCAI Conference 2011 Conference Paper

Dynamics of Profit-Sharing Games

  • John Augustine
  • Ning Chen
  • Edith Elkind
  • Angelo Fanelli
  • Nikolay Gravin
  • Dmitry Shiryaev

An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i. e. , work together in teams. In this paper, we study the dynamics of coalition formation under bounded rationality. We consider settings where each team's profit is given by a concave function, and propose three profit-sharing schemes, each of which is based on the concept of marginal utility. The agents are assumed to be myopic, i. e. , they keep changing teams as long as they can increase their payoff by doing so. We study the properties (such as closeness to Nash equilibrium or total profit) of the states that result after a polynomial number of such moves, and prove bounds on the price of anarchy and the price of stability of the corresponding games.

PDF Details DOI

TCS Journal 2010 Journal Article

When ignorance helps: Graphical multicast cost sharing games

  • Vittorio Bilò
  • Angelo Fanelli
  • Michele Flammini
  • Luca Moscardelli

In non-cooperative games played on highly decentralized networks the assumption that each player knows the strategy adopted by any other player may be too optimistic or even infeasible. In such situations, the set of players of which each player knows the chosen strategy can be modeled by means of a social knowledge graph in which nodes represent players and there is an edge from i to j if i knows j. Following the framework introduced in [7], we study the impact of social knowledge graphs on the fundamental multicast cost sharing game in which all the players want to receive the same communication from a given source in an undirected network. In the classical complete information case, such a game is known to be highly inefficient, since its price of anarchy can be as high as the total number of players ρ. We first show that, under our incomplete information setting, pure Nash equilibria always exist only if the social knowledge graph is directed acyclic (DAG). We then prove that the price of stability of any DAG is at least 1 2 log ρ and provide a DAG lowering the classical price of anarchy to a value between 1 2 log ρ and log 2 ρ. If specific instances of the game are concerned, that is if the social knowledge graph can be selected as a function of the instance, we show that the price of stability is at least 4 ρ ρ + 3, and that the same bound holds also for the price of anarchy of any social knowledge graph (not only DAGs). Moreover, we provide a nearly matching upper bound by proving that, for any fixed instance, there always exists a DAG yielding a price of anarchy less than 4. Our results open a new window on how the performances of non-cooperative systems may benefit from the lack of total knowledge among players.

Details DOI