Author name cluster

Cosimo Vinci

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.

18 papers

2 author rows

AAAI Conference 2026 Conference Paper

Approximately Envy-free and Equitable Allocations of Indivisible Items for Non-monotone Valuations

Vittorio Bilò
Martin Loebl
Cosimo Vinci

We revisit the setting of fair allocation of indivisible items among agents with heterogeneous, non-monotone valuations. We explore the existence and efficient computation of allocations that approximately satisfy either envy-freeness or equity constraints. Approximate envy-freeness ensures that each agent values her bundle at least as much as those given to the others, after some (or any) item removal, while approximate equity guarantees roughly equal valuations among agents, under similar adjustments. As a key technical contribution of this work, by leveraging fixed-point theorems (such as Sperner's Lemma and its variants), we establish the existence of envy-free-up-to-one-good-and-one-chore (EF1_g^c) and equitable-up-to-one-good-and-one-chore (EQ1_g^c) allocations, for non-monotone valuations that are always either non-negative or non-positive. These notions represent slight relaxations of the well-studied envy-free-up-to-one-item (EF1) and equitable-up-to-one-item (EQ1) guarantees, respectively. Our existential results hold even when items are arranged in a path and bundles must form connected sub-paths. The case of non-positive valuations, in particular, has been solved by proving a novel multi-coloring variant of Sperner's Lemma that constitutes a combinatorial result of independent interest. In addition, we also design a polynomial-time dynamic programming algorithm that computes an EQ1_g^c allocation. For monotone non-increasing valuations and path-connected bundles, all the above results can be extended to EF1 and EQ1 guarantees as well. Finally, we provide existential and computational results for certain stronger up-to-any-item equity notions under objective valuations, where items are partitioned into goods and chores.

PDF Details DOI

AAAI Conference 2026 Conference Paper

Greedily Maximizing Ex-Ante Fairness

Ruben Becker
Bojana Kodric
Cosimo Vinci

We study a general framework of optimization with the aim to compute fair solutions in settings with a set of agents whose valuations are combined using an aggregation function. The strength of our framework lies (1) in its generality and (2) in the fact that we leverage the power of ex-ante fairness, a concept that has recently gained much attention in the scope of fair allocation and fairness in AI in general. More precisely, in our setting there are n set functions f₁, …, fₙ (e.g., the valuation functions of n agents) that are combined using an aggregation function g (e.g., the minimum, Nash social welfare, p-norm). The power of ex-ante fairness is obtained by allowing as a feasible solution not simply a finite set S, but instead a distribution Π over feasible sets. The goal in our setting is then to find a probability distribution p in Π that maximizes the value resulting from aggregating (using g) the n expected values of the functions f₁, …, fₙ obtained when sampling a set S according to the distribution p. We stress that this is different from maximizing the expected value of g (ex-post fairness) and typically allows for much fairer solutions. We give three different greedy algorithms for three different settings of this framework and prove that they achieve constant approximation guarantees under certain realistic assumptions. For some of the settings, we show that these approximation guarantees are tight. Specific scenarios that can be modelled using our framework include fair information diffusion in social networks, fair submodular matching problems, and ex-ante versions of item assignment problems.

PDF Details DOI

TCS Journal 2026 Journal Article

Utility-sharing games: How to improve the efficiency with limited subsidies

Vittorio Bilò
Lucaleonardo Bove
Cosimo Vinci

In this work, we consider the problem of improving the efficiency of utility-sharing games, by resorting to a limited amount of subsidies. Utility-sharing games model scenarios in which strategic and self-interested players interact with each other by selecting resources. Each resource produces a utility that depends on the number of players selecting it, as a non-negative, non-decreasing and concave function, and each of these players receives an equal share of this utility. As the players’ selfish behavior may lead to pure Nash equilibria whose total utility is sub-optimal, previous work has resorted to subsidies, incentivizing the use of some resources, to contrast this phenomenon. We focus on the case in which the budget used to provide subsidies is bounded. We consider a class of mechanisms, called α-subsidy mechanisms, that allocate the budget in such a way that each player’s payoff is re-scaled up to a factor α ≥ 1. We design a specific sub-class of α-subsidy mechanisms, that can be implemented efficiently and distributedly by each resource, and evaluate their efficiency by providing upper bounds on their price of anarchy. These bounds are parametrized by both α and the underlying utility functions and are shown to be best-possible for α-subsidy mechanisms. Finally, we apply our results to the particular case of monomial utility functions of degree p ∈ (0, 1), and derive bounds on the price of anarchy that are parametrized by p and α.

Details DOI

AAMAS Conference 2025 Conference Paper

Adaptive Multi-Round Influence Maximization with Limited Information

Vincenzo Auletta
Francesco Carbone
Diodato Ferraioli
Cosimo Vinci

The Influence Maximization problem is a classic and well-studied problem in the area of Social Networks Analysis. In this problem you have a social network, a given information diffusion model, and a budget 𝐵, and you have to select a set of at most 𝐵 nodes (seeds) to activate in order to start an information diffusion campaign that is able to reach the (expected) largest number of nodes in the network. Recently, to better model viral marketing scenarios where advertisers conduct multiple rounds of viral marketing to promote one product, attention has been given to the adaptive and the multi-round versions of the problem. Here the campaign is orchestrated on a horizon of 𝑇 rounds and at the beginning of each round a different set of seeds is activated that can be adaptively selected given the results of the previous rounds. In this paper we generalize this setting to the case where the diffusion probabilities of the links in the network are not known in advance and they have to be learned while the campaign is running. We study the problem under the lens of online bandit algorithms, and we propose an online learning algorithm that is able to achieve a constant approximation of the optimal solution with only constant regret with respect to 𝑇. We also propose an alternative approach and we give preliminary experimental evidence that this outperforms our online learning algorithm in terms of computational complexity, keeping the regret sublinear.

PDF

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

AAMAS Conference 2024 Conference Paper

Approximately Fair Allocation of Indivisible Items with Random Valuations

Alessandro Aloisio
Vittorio Bilò
Antonio Mario Caruso
Michele Flammini
Cosimo Vinci

In this work, we consider the problem of fairly allocating a set of indivisible items to agents, who have additive and random valuations for the bundles of items they receive. The valuations that each agent has for all items are independent and bounded, and their realizations are only revealed after allocating the items. The goal is to determine an allocation that minimizes, in expectation, the maximum envy that an agent has for the bundle assigned to each other, without knowing in advance the realization of the random valuations. We first show how to compute in polynomial time and deterministically an allocation that guarantees an expected maximum envy of at most 𝑂(𝑤 p ln(𝑛)𝑚/𝑛), where 𝑛 is the number of agents, 𝑚 is the number of items and 𝑤 is the maximum valuation for each item. Furthermore, we show that the above bound cannot be improved, that is, there is an instance for which the expected maximum envy of any allocation is at least Ω(𝑤 p ln(𝑛)𝑚/𝑛). Finally, we resort to randomized algorithms that return (random) allocations satisfying further efficiency guarantees, such as ex-ante envy-freeness and ex-ante Pareto optimality. If we relax the constraint of ex-ante Pareto optimality, we provide an algorithm that still works without knowing the probability distributions of agent valuations.

PDF

AAAI Conference 2024 Conference Paper

Enhancing the Efficiency of Altruism and Taxes in Affine Congestion Games through Signalling

Vittorio Bilò
Cosimo Vinci

We address the problem of improving the worst-case efficiency of pure Nash equilibria (aka, the price of anarchy) in affine congestion games, through a novel use of signalling. We assume that, for each player in the game, a most preferred strategy is publicly signalled. This can be done either distributedly by the players themselves, or be the outcome of some centralized algorithm. We apply this signalling scheme to two well-studied scenarios: games with partially altruistic players and games with resource taxation. We show a significant improvement in the price of anarchy of these games, whenever the aggregate signalled strategy profile is a good approximation of the game social optimum.

PDF 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

AIJ Journal 2023 Journal Article

Better bounds on the adaptivity gap of influence maximization under full-adoption feedback

Gianlorenzo D'Angelo
Debashmita Poddar
Cosimo Vinci

In the influence maximization (IM) problem, we are given a social network and a budget k, and we look for a set of k nodes in the network, called seeds, that maximize the expected number of nodes that are reached by an influence cascade generated by the seeds, according to some stochastic model for influence diffusion. Extensive studies have been done on the IM problem, since this definition by Kempe et al. [26]. However, most of the work focuses on the non-adaptive version of the problem where all the k seed nodes must be selected before the cascade starts. In this paper we study the adaptive IM, where the nodes are selected sequentially one by one, and the decision on the i-th seed can be based on the observed cascade produced by the first i − 1 seeds. We focus on the full-adoption feedback in which we can observe the entire cascade of each previously selected seed under the independent cascade model where each edge is associated with an independent probability of diffusing influence. Previous works showed that there are constant upper bounds on the adaptivity gap, which compares the performance of an adaptive algorithm against a non-adaptive one, but the analyses used to prove these bounds only work for specific graph classes such as in-arborescences, out-arborescences, and one-directional bipartite graphs. Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by n 3 + 1, where n is the number of nodes in the graph. Moreover, we improve over the known upper bound for in-arborescences from 2 e / ( e − 1 ) ≈ 3. 16 to 2 e 2 / ( e 2 − 1 ) ≈ 2. 31. Then, we consider ( β, γ ) -bounded-activation graphs, where all nodes but β influence in expectation at most γ ∈ [ 0, 1 ) neighbors each; for this class of influence graphs we show that the adaptivity gap is at most β + 1 1 − γ. Finally, we study α-bounded-degree graphs, that is the class of undirected graphs in which the sum of node degrees higher than two is at most α, and show that the adaptivity gap is upper-bounded by α + O ( 1 ); we also show that in 0-bounded-degree graphs, i. e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most 3 e 3 / ( e 3 − 1 ) ≈ 3. 16. To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest.

Details DOI

TCS Journal 2023 Journal Article

Congestion games with priority-based scheduling

Vittorio Bilò
Cosimo Vinci

We reconsider atomic and non-atomic affine congestion games under the assumption that players are partitioned into p priority classes and resources schedule their users according to a priority-based policy, breaking ties uniformly at random. We derive tight bounds on both the price of anarchy and the price of stability as a function of p, revealing an interesting separation between the general case of p ≥ 2 and the priority-free scenario of p = 1. In fact, while in absence of priorities the worst-case prices of anarchy and stability of non-atomic games are lower than their counterparts in atomic ones, the two classes share the same bounds when p ≥ 2. Moreover, while the worst-case price of stability is lower than the worst-case price of anarchy in atomic games with no priorities, their values become equal when p ≥ 2. Said differently, the presence of priorities simultaneously irons out any combinatorial difference between atomic and non-atomic requests and among different pure Nash equilibria to produce a unique representative worst-case situation. Notably, our results keep holding even under singleton strategies. Besides being of independent interest, priority-based scheduling shares tight connections with online load balancing and finds a natural application within the theory of coordination mechanisms and cost-sharing policies for congestion games. Under this perspective, a number of possible research directions also arise.

Details DOI

IJCAI Conference 2022 Conference Paper

General Opinion Formation Games with Social Group Membership

Vittorio Bilò
Diodato Ferraioli
Cosimo Vinci

Modeling how agents form their opinions is of paramount importance for designing marketing and electoral campaigns. In this work, we present a new framework for opinion formation which generalizes the well-known Friedkin-Johnsen model by incorporating three important features: (i) social group membership, that limits the amount of influence that people not belonging to the same group may lead on a given agent; (ii) both attraction among friends, and repulsion among enemies; (iii) different strengths of influence lead from different people on a given agent, even if the social relationships among them are the same. We show that, despite its generality, our model always admits a pure Nash equilibrium which, under opportune mild conditions, is even unique. Next, we analyze the performances of these equilibria with respect to a social objective function defined as a convex combination, parametrized by a value λ∈[0, 1], of the costs yielded by the untruthfulness of the declared opinions and the total cost of social pressure. We prove bounds on both the price of anarchy and the price of stability which show that, for not-too-extreme values of λ, performance at equilibrium are very close to optimal ones. For instance, in several interesting scenarios, the prices of anarchy and stability are both equal to max{2λ, 1-λ}/min{2λ, 1-λ} which never exceeds 2 for λ∈[1/5, 1/2].

PDF Details DOI

AAAI Conference 2021 Conference Paper

Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback

Gianlorenzo D'Angelo
Debashmita Poddar
Cosimo Vinci

In the influence maximization (IM) problem, we are given a social network and a budget 𝑘, and we look for a set of 𝑘 nodes in the network, called seeds, that maximize the expected number of nodes that are reached by an influence cascade generated by the seeds, according to some stochastic model for influence diffusion. Extensive studies have been done on the IM problem, since his definition by Kempe, Kleinberg, and Tardos (2003). However, most of the work focuses on the nonadaptive version of the problem where all the 𝑘 seed nodes must be selected before that the cascade starts. In this paper we study the adaptive IM, where the nodes are selected sequentially one by one, and the decision on the 𝑖-th seed can be based on the observed cascade produced by the first 𝑖 − 1 seeds. We focus on the full-adoption feedback in which we can observe the entire cascade of each previously selected seed and on the independent cascade model where each edge is associated with an independent probability of diffusing influence. Previous works showed that there are constant upper bounds on the adaptivity gap, which compares the performance of an adaptive algorithm against a non-adaptive one, but the analyses used to prove these bounds only works for specific graph classes such as in-arborescences, out-arborescences, and one-directional bipartite graphs. Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by 3 √ 𝑛 + 1, where 𝑛 is the number of nodes in the graph. Moreover we improve over the known upper bound for in-arborescences from 2𝑒/(𝑒 − 1) ≈ 3. 16 to 2𝑒2/(𝑒2 − 1) ≈ 2. 31. Finally, we study 𝛼-bounded graphs, a class of undirected graphs in which the sum of node degrees higher than two is at most 𝛼, and show that the adaptivity gap is upper-bounded by √ 𝛼 + 𝑂(1). Moreover, we show that in 0-bounded graphs, i. e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most 3𝑒3/(𝑒3 − 1) ≈ 3. 16. To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest.

PDF Details

IJCAI Conference 2021 Conference Paper

Distance Polymatrix Coordination Games

Alessandro Aloisio
Michele Flammini
Bojana Kodric
Cosimo Vinci

In polymatrix coordination games, each player x is a node of a graph and must select an action in her strategy set. Nodes are playing separate bimatrix games with their neighbors in the graph. Namely, the utility of x is given by the preference she has for her action plus, for each neighbor y, a payoff which strictly depends on the mutual actions played by x and y. We propose the new class of distance polymatrix coordination games, properly generalizing polymatrix coordination games, in which the overall utility of player x further depends on the payoffs arising by mutual actions of players v, z that are the endpoints of edges at any distance h<d from x, for a fixed threshold value d≤n. In particular, the overall utility of player x is the sum of all the above payoffs, where each payoff is proportionally discounted by a factor depending on the distance h of the corresponding edge. Under the above framework, which is a natural generalization that is well-suited for capturing positive community interactions, we study the social inefficiency of equilibria resorting to standard measures of Price of Anarchy and Price of Stability. Namely, we provide suitable upper and lower bounds for the aforementioned quantities, both for bounded-degree and general graphs.

PDF Details DOI

ECAI Conference 2020 Conference Paper

Inequity Aversion Pricing in Multi-Unit Markets

Michele Flammini
Manuel Mauro
Matteo Tonelli
Cosimo Vinci

We build upon previous models for differential pricing in social networks and fair price discrimination in markets, considering a setting in which multiple units of a single product must be sold to selected buyers so as to maximize the seller’s revenue or the social welfare, while limiting the differences of the prices offered to social neighbors. We first consider the case of general social graph topologies, and provide optimal or nearly-optimal hardness and approximation results for the related optimization problems under various meaningful assumptions, including the inapproximability within any constant factor on the achievable revenue under the unique game conjecture. Then, we focus on topologies that are typical of social networks. Namely, we consider graphs where the node degrees follow a power-law distribution, and show that it is possible to obtain constant or good approximations for the seller’s revenue maximization with high probability, thus improving upon the general case.

Details

AAAI Conference 2020 Conference Paper

The Impact of Selfishness in Hypergraph Hedonic Games

Alessandro Aloisio
Michele Flammini
Cosimo Vinci

We consider a class of coalition formation games that can be succinctly represented by means of hypergraphs and properly generalizes symmetric additively separable hedonic games. More precisely, an instance of hypegraph hedonic game consists of a weighted hypergraph, in which each agent is associated to a distinct node and her utility for being in a given coalition is equal to the sum of the weights of all the hyperedges included in the coalition. We study the performance of stable outcomes in such games, investigating the degradation of their social welfare under two different metrics, the k-Nash price of anarchy and k-core price of anarchy, where k is the maximum size of a deviating coalition. Such prices are deﬁned as the worst-case ratio between the optimal social welfare and the social welfare obtained when the agents reach an outcome satisfying the respective stability criteria. We provide asymptotically tight upper and lower bounds on the values of these metrics for several classes of hypergraph hedonic games, parametrized according to the integer k, the hypergraph arity r and the number of agents n. Furthermore, we show that the problem of computing the exact value of such prices for a given instance is computationally hard, even in case of non-negative hyperedge weights.

PDF Details

TCS Journal 2020 Journal Article

The price of anarchy of affine congestion games with similar strategies

Vittorio Bilò
Cosimo Vinci

Affine congestion games are a well-studied model for selfish behavior in distributed systems, such as transportation and communication networks. Seminal influential papers in Algorithmic Game Theory have bounded the worst-case inefficiency of Nash equilibria, termed as price of anarchy, in several variants of these games. In this work, we investigate to what extent these bounds depend on the similarities among the players' strategies. Our notion of similarity is modeled by assuming that, given a parameter θ ≥ 1, the costs of any two strategies available to a same player, when evaluated in absence of congestion, are within a factor θ one from the other. It turns out that, for the non-atomic case, better bounds can always be obtained for any finite value of θ. For the atomic case, instead, θ < 3 / 2 and θ < 2 are necessary and sufficient conditions to obtain better bounds in games played on general graph topologies and on parallel link graphs, respectively. It is worth noticing that small values of θ model the behavioral attitude of players who are partially oblivious to congestion and are not willing to significantly deviate from what is their best strategy in absence of congestion.

Details DOI

ECAI Conference 2020 Conference Paper

The Quality of Content Publishing in the Digital Era

Vittorio Bilò
Michele Flammini
Cosimo Vinci

We propose and analyse a game describing the interactions between readers and publishers, with the aim of understanding to what extent the strategic behaviour of the latter may influence the quality of content publishing in the World Wide Web. For games with identical publishers, we provide a wide characterization of the cases in which pure Nash equilibria are guaranteed to exist, which mainly depends on the number of publishers and, subordinately, on some of the parameters we use to model their writing abilities. Then, for any game possessing pure Nash equilibria, we show that the price of anarchy is at most 2, even in presence of heterogeneous publishers. Finally, we provide better and tight bounds for some special cases of games with identical publishers.

Details

TCS Journal 2019 Journal Article

Non-atomic one-round walks in congestion games

Cosimo Vinci

In this paper we study the approximation ratio of the solutions achieved after an ϵ-approximate one-round walk in non-atomic congestion games. Prior to this work, the solution concept of one-round walks had been studied for atomic congestion games with linear latency functions only (Christodoulou et al. [1], Bilò et al. [2]). We give an explicit formula to determine the approximation ratio for non-atomic congestion games having general latency functions. In particular, we focus on polynomial latency functions, and, we prove that the approximation ratio is exactly ( ( 1 + ϵ ) ( p + 1 ) ) p + 1 for every polynomial of degree p. Then, we show that, by resorting to static (resp. dynamic) resource taxation, the approximation ratio can be lowered to ( 1 + ϵ ) p + 1 ( p + 1 ) p (resp. ( 1 + ϵ ) p + 1 ( p + 1 )! ).

Details DOI