Author name cluster

Luca Moscardelli

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.

27 papers

2 author rows

AAAI Conference 2026 Conference Paper

Compensate to Not Deviate: On Subsidised Equilibria

Vittorio Bilò
Gianpiero Monaco
Luca Moscardelli

We introduce a new notion of deterministic stable solution for non-cooperative games, termed subsidized equilibrium. It assumes that an amount of money can be used as a pool of subsidies to stabilize a strategy profile that otherwise would not be accepted by (some of) the players. Roughly speaking, for a given amount of money, a strategy profile is a subsidized equilibrium if the total payoff loss incurred by players not playing best-responses does not exceed that amount, i.e., there is enough money to refund all players experiencing a regret. With respect to many other solution concepts in the literature, the notion of subsidized equilibrium has important advantages. Specifically, for a sufficiently high value of money, a subsidized equilibrium always exists and can even be computed in polynomial time; also, existence of an efficient subsidized equilibrium can be guaranteed. Thus, determining for which amounts of money existence, polynomial time computability and efficiency can or cannot be achieved becomes an intriguing question. We provide initial results towards this direction for some widely studied classes of games.

PDF Details DOI

ECAI Conference 2025 Conference Paper

Approximately Stable Matching

Angelo Fanelli 0001
Luca Moscardelli

Many allocation and matching problems (e. g. , student-school assignments, job allocation, organ donation) involve coupling agents based on mutual preferences. A central requirement in matching problems is that of stability, that is classically defined as follows: a matching is stable if no blocking pair exists, where a blocking pair is a pair of agents preferring each other over their assigned partners. We assume that matchings are constrained by a given undirected acceptability graph: two agents may be matched only if they are connected by an edge. While stable matchings are guaranteed for specific graph topologies, such as bipartite graphs, stability is not always achievable in more general scenarios. In this paper, we introduce a relaxed notion of stability, yielding to the study of approximately stable matching. Specifically, we define a matching as approximately stable if there exists no k-blocking pair, i. e. , no pair of agents who could both improve their assigned partners by at least k positions in their respective preference rankings, by forming a new match together. This refinement captures the idea that small agent gains may not justify a deviation. We provide some theoretical results about the existence and computability of approximately stable matchings, revealing their strengths as well as their inherent limitations. We believe that the introduced notion of approximate stability, along with our foundational findings, constitute a solid basis for future research on matching problems.

Details

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

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

AAMAS Conference 2024 Conference Paper

On Green Sustainability of Resource Selection Games with Equitable Cost-Sharing

Vittorio Bilò
Michele Flammini
Gianpiero Monaco
Luca Moscardelli
Cosimo Vinci

As increasing concern for environmental sustainability urges to bring attention to green-aware multi-agent systems, we put forward a game-theoretic model in which agents compete for the usage of power-consuming resources and are charged a cost proportional to their fair share of the power consumption. Using the widely adopted cube-root rule for CMOS-based devices, our model becomes a congestion game in which two distinct parts coexist, namely, congestion games with polynomial latency functions and fair cost-sharing games. The interplay between these two components is governed by two resource-specific constants regulating the static and dynamic power consumption of each resource. Our findings show that, despite these games being highly inefficient in the general case (a super-constant price of stability), performance at equilibrium significantly improves (a constant price of anarchy) when the ratio between the static and dynamic power consumption of each resource remains bounded by a constant. This suggests that, in uncoordinated green-aware multi-agent systems, technology plays a fundamental role in shaping the efficiency of stable solutions.

PDF

AAAI Conference 2022 Conference Paper

Hedonic Games with Fixed-Size Coalitions

Vittorio Bilò
Gianpiero Monaco
Luca Moscardelli

In hedonic games, a set of n agents, having preferences over all possible coalition structures, needs to agree on a stable outcome. In this work, we initiate the study of hedonic games with fixed-size coalitions, where the set of possible coalition structures is restricted as follows: there are k coalitions, each coalition has a fixed size, and the sum of the sizes of all coalitions equals n. We focus on the basic model of additively separable hedonic games with symmetric preferences, where an agent’s preference is captured by a utility function which sums up a contribution due to any other agent in the same coalition. In this setting, an outcome is stable if no pair of agents can exchange coalitions and improve their utilities. Conditioned on the definition of improvement, three stability notions arise: swap stability under transferable utilities, which requires to improve the sum of the utilities of both agents, swap stability, which requires to improve the utility of one agent without decreasing the utility of the other one, and strict swap stability, requiring to improve the utilities of both agents simultaneously. We analyse the fundamental questions of existence, complexity and efficiency of stable outcomes, and that of complexity of a social optimum.

PDF Details

JAIR Journal 2022 Journal Article

Pricing Problems with Buyer Preselection

Vittorio Bilò
Michele Flammini
Gianpiero Monaco
Luca Moscardelli

We investigate the problem of preselecting a subset of buyers (also called agents) participating in a market so as to optimize the performance of stable outcomes. We consider four scenarios arising from the combination of two stability notions, namely market envy-freeness and agent envy-freeness, with the two state-of-the-art objective functions of social welfare and seller’s revenue. When insisting on market envy-freeness, we prove that the problem cannot be approximated within n 1−ε (with n being the number of buyers) for any ε > 0, under both objective functions; we also provide approximation algorithms with an approximation ratio tight up to subpolynomial multiplicative factors for social welfare and the seller’s revenue. The negative result, in particular, holds even for markets with single-minded buyers. We also prove that maximizing the seller’s revenue is NP-hard even for a single buyer, thus closing a previous open question. Under agent envy-freeness and for both objective functions, instead, we design a polynomial time algorithm transforming any stable outcome for a market involving any subset of buyers into a stable outcome for the whole market without worsening its performance. This result creates an interesting middle-ground situation where, if on the one hand buyer preselection cannot improve the performance of agent envy-free outcomes, on the other one it can be used as a tool for simplifying the combinatorial structure of the buyers’ valuation functions in a given market. Finally, we consider the restricted case of multi-unit markets, where all items are of the same type and are assigned the same price. For these markets, we show that preselection may improve the performance of stable outcomes in all of the four considered scenarios, and design corresponding approximation algorithms.

PDF Details DOI

JAIR Journal 2021 Journal Article

On the Online Coalition Structure Generation Problem

Michele Flammini
Gianpiero Monaco
Luca Moscardelli
Mordechai Shalom
Shmuel Zaks

We consider the online version of the coalition structure generation problem, in which agents, corresponding to the vertices of a graph, appear in an online fashion and have to be partitioned into coalitions by an authority (i.e., an online algorithm). When an agent appears, the algorithm has to decide whether to put the agent into an existing coalition or to create a new one containing, at this moment, only her. The decision is irrevocable. The objective is partitioning agents into coalitions so as to maximize the resulting social welfare that is the sum of all coalition values. We consider two cases for the value of a coalition: (1) the sum of the weights of its edges, and (2) the sum of the weights of its edges divided by its size. Coalition structures appear in a variety of application in AI, multi-agent systems, networks, as well as in social networks, data analysis, computational biology, game theory, and scheduling. For each of the coalition value functions we consider the bounded and unbounded cases depending on whether or not the size of a coalition can exceed a given value α. Furthermore, we consider the case of a limited number of coalitions and various weight functions for the edges, i.e., unrestricted, positive and constant weights. We show tight or nearly tight bounds for the competitive ratio in each case.

PDF 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

AAMAS Conference 2019 Conference Paper

Local Core Stability in Simple Symmetric Fractional Hedonic Games

Raffaello Carosi
Gianpiero Monaco
Luca Moscardelli

We initiate the study of local core stability in simple symmetric fractional hedonic games. The input is an unweighted undirected graph G where vertices are the agents and edges model social connection (i. e. , acquaintance) among agents. We assume that if there is an edge between two agents then they value 1 each other otherwise they value 0 each other, i. e. , we consider the simple setting where an agent values 1 all and only her acquaintances. A coalition structure is a partition of the agents into coalitions where the utility of an agent is equal to the number of agents inside her coalition that are valued 1 divided by the size of the coalition. A coalition structure is in the core if no subset of agents can strictly improve all their utility by forming a new coalition together. In [7] it is shown that simple symmetric fractional hedonic games may not admit a core stable coalition structure. However, the fact that the core is required to be resilient to deviations by any groups of agents could be sometimes unrealistic, especially in systems with large populations. In fact, it may be difficult that agents are able to coordinate each other in order to understand whether there is the possibility of deviating together. Motivated by the above considerations, we define a relaxation of the core, called local core. A coalition structure is in the local core if there is no subset of agents which (1) induces a clique in the graph G and (2) such that all agents can improve their utility by forming a new coalition together. We first show that any local core dynamics converges, which implies that a local core stable coalition structure always exists. We then study its performance with respect to the classic utilitarian social welfare and provide tight and almost tight bounds on the local core price of anarchy and stability, respectively.

PDF

AAMAS Conference 2019 Conference Paper

On the Performance of Stable Outcomes in Modified Fractional Hedonic Games with Egalitarian Social Welfare

Gianpiero Monaco
Luca Moscardelli
Yllka Velaj

In this paper we consider modified fractional hedonic games, that are coalition formation games defined over an undirected edgeweighted graph G = (N, E, w), where N is the set of agents and for any edge {u, v} ∈ E, wu, v = wv, u reflects how much agents u and v benefit from belonging to the same coalition. More specifically, given a coalition structure, i. e. , a partition of the agents into coalitions, the utility of an agent u is given by the sum of wu, v over all other agents v belonging to the same coalition of u averaged over all other members of that coalition, i. e. , excluding herself. We focus on common stability notions: we are interested in strong Nash stable, Nash stable and core stable outcomes. In [18], the existence of these natural outcomes for modified fractional hedonic games is completely characterized; moreover, many tight or asymptotically tight results on their performance are shown for the classical utilitarian social welfare function, that is defined as the sum of all agents’ utilities. Motivated by the fact that an outcome with an high utilitarian social welfare could be extremely harsh for some agents, we provide a comprehensive analysis on the performance of strong Nash stable, Nash stable and core stable outcomes for modified fractional hedonic games under the egalitarian social welfare function, that is defined as the minimum among all agents’ utilities.

PDF

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

JAAMAS Journal 2019 Journal Article

Stable outcomes in modified fractional hedonic games

Gianpiero Monaco
Luca Moscardelli
Yllka Velaj

Abstract In coalition formation games self-organized coalitions are created as a result of the strategic interactions of independent agents. In this paper we assume that for each couple of agents ( i, j ), weight \(w_{i, j}=w_{j, i}\) reflects how much agents i and j benefit from belonging to the same coalition. We consider the (symmetric) modified fractional hedonic game, that is a coalition formation game in which agents’ utilities are such that the total benefit of agent i belonging to a coalition (given by the sum of \(w_{i, j}\) over all other agents j belonging to the same coalition) is averaged over all the other members of that coalition, i. e. , excluding herself. Modified fractional hedonic games constitute a class of succinctly representable hedonic games. We are interested in the scenario in which agents, individually or jointly, choose to form a new coalition or to join an existing one, until a stable outcome is reached. To this aim, we consider common stability notions leading to strong Nash stable outcomes, Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general weights and in the case of 0–1 weights. In particular, we completely characterize the existence of the considered stable outcomes and show many tight or asymptotically tight results on the performance of these natural stable outcomes for modified fractional hedonic games, also highlighting the differences with respect to the model of fractional hedonic games, in which the total benefit of an agent in a coalition is averaged over all members of that coalition, i. e. , including herself.

Details DOI

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

AAMAS Conference 2018 Conference Paper

On the Impact of Buyers Preselection in Pricing Problems

Vittorio Bil�
Michele Flammini
Gianpiero Monaco
Luca Moscardelli

We investigate the problem of preselecting a subset of buyers participating in a market so as to optimize the performance of stable outcomes. We consider four scenarios arising from the combination of two stability notions, item and bundle envy-freeness, with the two classical objective functions, i. e. , the social welfare and the seller’s revenue. When adopting the notion of item envy-freeness, we prove that, for both the two objective functions, the problem cannot be approximated within n1−ε for any ε > 0, and provide tight or nearly tight approximation algorithms. We also prove that maximizing the seller’s revenue is NP-hard even for a single buyer, thus closing a longstanding open question. Under bundle envyfreeness, instead, we show how to transform in polynomial time any stable outcome for a market involving only a subset of buyers to a stable one for the whole market without worsening its performance, both for the social welfare and the seller’s revenue. This transformation implies that, although in this case buyer preselection cannot improve the performance, it can still be used as an algorithmic tool for computing good stable outcomes when preselection is not allowed. In fact, it can be first exploited to simplify the combinatorics of the problem, and then for mapping back the computed solution to one encompassing all the buyers. Finally, we consider multi-unit markets, where all items are of the same type and are assigned the same price. For this specific case, we show that buyer preselection can improve the performance of stable outcomes in all of the four considered scenarios, and design corresponding approximation algorithms.

PDF

AAMAS Conference 2018 Conference Paper

Online Coalition Structure Generation in Graph Games

Michele Flammini
Gianpiero Monaco
Luca Moscardelli
Mordechai Shalom
Shmuel Zaks

We consider the online version of the coalition structure generation in graph games problem, where agents are vertices in a graph. After each step t, in which the t-th agent appears in an online fashion, agents are partitioned into c(t) coalitions C(t) = {Ct 1, Ct 2, .. ., Ct c(t) }, such that every agent belongs to exactly one coalition Ct i. When an agent appears, it may either join an existing coalition or form a new one having it as the only agent. The profit of a such a coalition structure C(t) is the sum of the profits of its coalitions. We consider two cases for the profit of a coalition: (1) the sum of the weights of its edges (which represents the total profit of the agents in the coalition), and (2) the sum of the weights of its edges divided by its size (which represents the average profit of the agents in the coalition). Such coalition structures appear in a variety of application in AI, multi-agent systems, networks, as well as in social networks, data analysis, computational biology, game theory, and scheduling. For each of the profit functions we consider the bounded and unbounded cases depending on whether or not the size of a coalition can exceed a given value α. Furthermore, we consider the case of a limited number of coalitions and various weight functions for the edges, namely the cases of unrestricted, positive and constant weights. We show tight or nearly tight bounds for the competitive ratio in each case.

PDF

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

MFCS Conference 2018 Conference Paper

Pricing Problems with Buyer Preselection

Vittorio Bilò
Michele Flammini
Gianpiero Monaco
Luca Moscardelli

We investigate the problem of preselecting a subset of buyers participating in a market so as to optimize the performance of stable outcomes. We consider four scenarios arising from the combination of two stability notions, item and bundle envy-freeness, with the two classical objective functions, i. e. , the social welfare and the seller's revenue. When adopting the notion of item envy-freeness, we prove that, for both the two objective functions, the problem cannot be approximated within n^(1-epsilon) for any epsilon >0, and provide tight or nearly tight approximation algorithms. We also prove that maximizing the seller's revenue is NP-hard even for a single buyer, thus closing an open question. Under bundle envy-freeness, instead, we show how to transform in polynomial time any stable outcome for a market involving only a subset of buyers to a stable one for the whole market without worsening its performance, both for the social welfare and the seller's revenue. Finally, we consider multi-unit markets, where all items are of the same type and are assigned the same price. For this specific case, we show that buyer preselection can improve the performance of stable outcomes in all of the four considered scenarios, and we design corresponding approximation algorithms.

Details

AAMAS Conference 2018 Conference Paper

Stable Outcomes in Modified Fractional Hedonic Games

Gianpiero Monaco
Luca Moscardelli
Yllka Velaj

In coalition formation games self-organized coalitions are created as a result of the strategic interactions of independent agents. For each couple of agents (i, j), weight wi, j = wj, i reflects how much agents i and j benefit from belonging to the same coalition. We consider the modified fractional hedonic game, that is a coalition formation game in which agents’ utilities are such that the total benefit of agent i belonging to a coalition (given by the sum of wi, j over all other agents j belonging to the same coalition) is averaged over all the other members of that coalition, i. e. , excluding herself. Modified fractional hedonic games constitute a class of succinctly representable hedonic games. We are interested in the scenario in which agents, individually or jointly, choose to form a new coalition or to join an existing one, until a stable outcome is reached. To this aim, we consider common stability notions, leading to strong Nash stable outcomes, Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general weights and in the case of 0-1 weights. In particular, we completely characterize the existence of the considered stable outcomes and show many tight or asymptotically tight results on the performance of these natural stable outcomes for modified fractional hedonic games, also highlighting the differences with respect to the model of fractional hedonic games, in which the total benefit of an agent in a coalition is averaged over all members of that coalition, i. e. , including herself.

PDF

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

FOCS Conference 2013 Conference Paper

The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation Is Constant

Vittorio Bilò
Michele Flammini
Luca Moscardelli

We consider broadcast network design games in undirected networks in which every player is a node wishing to receive communication from a distinguished source node s and the cost of each communication link is equally shared among the downstream receivers according to the Shapley value. We prove that the Price of Stability of such games is constant, thus closing a long-standing open problem raised in [2]. Our result is obtained by means of homogenization, a new technique that, in any intermediate state locally diverging from a given optimal solution T*, is able to restore local similarity by exploiting cost differences between nearby players in T*.

Details

MFCS Conference 2012 Conference Paper

On the Impact of Fair Best Response Dynamics

Angelo Fanelli 0001
Luca Moscardelli
Alexander Skopalik

Abstract In this work we completely characterize how the frequency with which each player participates in the game dynamics affects the possibility of reaching efficient states, i. e. , states with an approximation ratio within a constant factor from the price of anarchy, within a polynomially bounded number of best responses. We focus on the well known class of linear congestion games and we show that (i) if each player is allowed to play at least once and at most β times in T best responses, states with approximation ratio O ( β ) times the price of anarchy are reached after T ⌈loglog n ⌉ best responses, and that (ii) such a bound is essentially tight also after exponentially many ones. One important consequence of our result is that the fairness among players is a necessary and sufficient condition for guaranteeing a fast convergence to efficient states. This answers the important question of the maximum order of β needed to fast obtain efficient states, left open by [10, 11] and [3], in which fast convergence for constant β and very slow convergence for β = O ( n ) have been shown, respectively. Finally, we show that the structure of the game implicitly affects its performances. In particular, we prove that in the symmetric setting, in which all players share the same set of strategies, the game always converges to an efficient state after a polynomial number of best responses, regardless of the frequency each player moves with. All the results extend to weighted congestion games.

Details

TCS Journal 2011 Journal Article

Optimizing regenerator cost in traffic grooming

Michele Flammini
Gianpiero Monaco
Luca Moscardelli
Mordechai Shalom
Shmuel Zaks

In optical networks, regenerators have to be placed on lightpaths every d consecutive nodes in order to regenerate the signal. In addition, grooming enables the use of the same regenerator by several lightpaths. Up to g (the grooming factor) lightpaths can use the same regenerator. In this work we consider the problem of minimizing the number of regenerators used in traffic grooming in optical networks. Starting from the 4 -approximation algorithm of Flammini et al. (2010) [10] for d = 1 and a path topology, we provide an approximation algorithm with the same approximation ratio for d = 1 and the ring and tree topologies. We present also a technique based on matching that leads to the same approximation ratio in tree topology and can be used to obtain approximation algorithms in other topologies. We provide an approximation algorithm for general topology that uses this technique. Finally, all the results are extended to the case of general d.

Details DOI

TCS Journal 2010 Journal Article

Minimizing total busy time in parallel scheduling with application to optical networks

Michele Flammini
Gianpiero Monaco
Luca Moscardelli
Hadas Shachnai
Mordechai Shalom
Tami Tamir
Shmuel Zaks

We consider a scheduling problem in which a bounded number of jobs can be processed simultaneously by a single machine. The input is a set of n jobs J = { J 1, …, J n }. Each job, J j, is associated with an interval [ s j, c j ] along which it should be processed. Also given is the parallelism parameter g ≥ 1, which is the maximal number of jobs that can be processed simultaneously by a single machine. Each machine operates along a contiguous time interval, called its busy interval, which contains all the intervals corresponding to the jobs it processes. The goal is to assign the jobs to machines so that the total busy time is minimized. The problem is known to be NP-hard already for g = 2. We present a 4 -approximation algorithm for general instances, and approximation algorithms with improved ratios for instances with bounded lengths, for instances where any two intervals intersect, and for instances where no interval is properly contained in another. Our study has application in optimizing the switching costs of optical networks.

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

MFCS Conference 2008 Conference Paper

When Ignorance Helps: Graphical Multicast Cost Sharing Games

Vittorio Bilò
Angelo Fanelli 0001
Michele Flammini
Luca Moscardelli

Abstract 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 unfeasible. 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 [3], we study the impact of social knowledge graphs on the fundamental multicast cost sharing game in which all the players wants to receive the same communication from a given source. Such a game in the classical complete information case 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 \(\frac 1 2\log\rho\) and provide a DAG lowering the classical price of anarchy to a value between \(\frac 1 2\log\rho\) 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 \(\frac{4\rho}{\rho+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 and can be considered, in some sense, as another evidence of the famous Braess’ paradox.

Details

MFCS Conference 2006 Conference Paper

Multicast Transmissions in Non-cooperative Networks with a Limited Number of Selfish Moves

Angelo Fanelli 0001
Michele Flammini
Giovanna Melideo
Luca Moscardelli

Abstract We study a multicast game in communication networks in which a source sends the same message or service to a set of destinations and the cost of the used links is divided among the receivers according to given cost sharing methods. Assuming a selfish and rational behavior, each receiving user is willing to select a strategy yielding the minimum shared cost. A Nash equilibrium is a solution in which no user can decrease its payment by adopting a different strategy, and the price of anarchy is defined as the worst case ratio between the overall communication cost yielded by an equilibrium and the minimum possible one. Nash equilibria requiring an excessive number of steps to be reached or being hard to compute or not existing at all, we are interested in the determination of the price of anarchy reached in a limited number of rounds, each of which containing at least one move per receiving user. We consider different reasonable cost sharing methods, including the well-known Shapley and egalitarian ones, and investigate their performances versus two possible global criteria: the overall cost of the used links and the maximum shared cost of users. We show that, even in case of two receivers making the best possible move at each step, the number of steps needed to reach a Nash equilibrium can be arbitrarily large. Moreover, we determine the cost sharing methods for which a single round is already sufficient to get a price of anarchy comparable to the one at equilibria, and the ones not satisfying such a property. Finally, we show that finding the sequence of moves leading to the best possible global performance after one-round is already an intractable problem, i. e. , NP-hard.

Details