Vittorio Bilò

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.

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.

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 α.

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.

JAIR Journal 2025 Journal Article

On a Simple Hedonic Game with Graph-Restricted Communication

• Vittorio Bilò
• Laurent Gourvès
• Jérôme Monnot

We study a hedonic game for which feasible coalitions are prescribed by a graph representing the agents’ social relations. A group of agents can form a feasible coalition if and only if their corresponding vertices can be spanned with a star. This requirement guarantees that agents are connected, close to each other, and one central agent can coordinate the actions of the group. In our game, everyone strives to join the largest feasible coalition. We study the existence and computational complexity of both Nash stable and core stable partitions. Then, we provide tight or asymptotically tight bounds on their efficiency, measured in terms of the price of anarchy and the price of stability, under two natural social functions, namely, the number of agents who are not in a singleton coalition, and the number of coalitions. We also derive refined bounds for games in which the social graph is claw-free. Finally, we investigate the complexity of computing socially optimal partitions, as well as extreme Nash stable ones.

MFCS Conference 2025 Conference Paper

On the Performance of Mildly Greedy Players in k-Coloring Games

• Vittorio Bilò
• Andrea D'Ascenzo
• Mattia D'Emidio
• Giuseppe F. Italiano

We study the performance of mildly greedy players in k-coloring games, a relevant subclass of anti-coordination games. A mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than ε, for some given ε ≥ 0. In presence of mildly greedy players, stability is captured by the concept of (1+ε)-approximate Nash equilibrium. In this paper, we first show that, for any k-coloring game, the (1+ε)-approximate price of anarchy, i. e. , the price of anarchy of (1+ε)-approximate pure Nash equilibria, is at least (k-1)/((k-1)ε +k), and that this bound is tight for any ε ≥ 0. Then, we evaluate the approximation ratio of the solutions achieved after a (1 + ϵ)-approximate one-round walk starting from any initial strategy profile, where a (1 + ϵ)-approximate one-round walk is a sequence of (1 + ε)-approximate best-responses, one for each player. We provide a lower bound of min{(k-2)/k, (k-1)/((k-1)ε+k)} on this ratio, for any ε ≥ 0 and k ≥ 5; for the cases of k = 3 and k = 4, we give finer bounds depending on ε. Our work generalizes the results known for cut games, the special case of k-coloring games restricted to k = 2.

TCS Journal 2025 Journal Article

The contest game for crowdsourcing reviews

• Vittorio Bilò
• Marios Mavronicolas
• Paul G. Spirakis

We consider a contest game with discrete strategies, modelling a contest where reviews for a proposal are crowdsourced from n players. Player i has a skill s i, strategically chooses a quality q ∈ { 1, 2, …, Q } for her review and pays an effort f q ≥ 0, strictly increasing with q. Under voluntary participation, a player may opt to not write a review, paying zero effort; mandatory participation excludes this option. For her effort, she is awarded a payment per her payment function, which is either player-invariant, like, e. g. , the popular proportional allocation, or player-specific; it is oblivious when it does not depend on the loads on other qualities. The utility to player i is the difference between her payment and her cost, calculated by a skill-effort function Λ ( s i, f q ). Skills may vary for arbitrary players; when players are anonymous, s i = 1 for each player i. In a pure Nash equilibrium, no player could increase her utility by unilaterally switching to another quality. We show the following results about the (in)existence and the computation of a pure Nash equilibrium: • A contest game with arbitrary players and player-invariant and oblivious payments is an unweighted congestion game with player-specific constants on parallel links [42]; so it has a generalized ordinal potential, the Finite Improvement Property (FIP) and a pure Nash equilibrium, which can be computed in PLS. However, under the assumption that the payment function is monotonically nonincreasing, a pure Nash equilibrium can be computed efficiently by resorting to [44, Theorem 2]. In contrast, a pure Nash equilibrium might not exist for (i) anonymous players and player-invariant but not oblivious payments, (ii) arbitrary players and proportionally allocated payments, and (iii) anonymous players and player-specific and oblivious payments; in the latter case, it is NP -hard to decide existence even if players are anonymous. These counterexamples prove the tightness of our existence result and suggest that the decision and search problems for a pure Nash equilibrium are computationally hard. • Under some mild assumptions on the efforts, the contest game with anonymous players and proportional allocation has at least one Nash equilibrium. For arbitrary players, we identify a simple condition involving both skills and efforts that suffices for the existence of a pure Nash equilibrium in the special case where the skill-effort function has the product form Λ ( s i, f q ) = s i f q. In both cases the pure Nash equilibrium is simple and computable in constant time. • Under the assumption that costs are player-consistent, there is a polynomial-time Θ ( n Q ) algorithm to decide the existence and compute a pure Nash equilibrium for constant Q, for the case of arbitrary players and player-invariant payments; so the computational problem is XP -tractable with respect to the parameter Q. Player-consistent costs means that all players are incurred the same relative costs for a given pair of qualities. The computed equilibrium is contiguous by design: players with higher skills are contiguously assigned to lower qualities. Our results indicate that the decision and search problems for pure Nash equilibria are likely to be computationally hard even in the simplest case, but can be made easy even in the hardest case by adopting simple assumptions on efforts, payments or costs, no matter whether participation is mandatory or voluntary.

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.

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.

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.

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.

TCS Journal 2023 Journal Article

Project games

• Vittorio Bilò
• Laurent Gourvès
• Jérôme Monnot

We consider a strategic game, called project game, where each agent has to choose a project among her own list of available projects. The model includes positive weights expressing the capacity of a given agent to contribute to a given project. The realization of a project produces some reward that has to be allocated to the agents. The reward of a realized project is fully allocated to its contributors according to a simple proportional rule. Existence and computational complexity of pure Nash equilibria is addressed and their efficiency is investigated according to both the utilitarian and the egalitarian social function.

IJCAI Conference 2023 Conference Paper

Schelling Games with Continuous Types

• Davide Bilò
• Vittorio Bilò
• Michelle Döring
• Pascal Lenzner
• Louise Molitor
• Jonas Schmidt

In most major cities and urban areas, residents form homogeneous neighborhoods along ethnic or socioeconomic lines. This phenomenon is widely known as residential segregation and has been studied extensively. Fifty years ago, Schelling proposed a landmark model that explains residential segregation in an elegant agent-based way. A recent stream of papers analyzed Schelling's model using game-theoretic approaches. However, all these works considered models with a given number of discrete types modeling different ethnic groups. We focus on segregation caused by non-categorical attributes, such as household income or position in a political left-right spectrum. For this, we consider agent types that can be represented as real numbers. This opens up a great variety of reasonable models and, as a proof of concept, we focus on several natural candidates. In particular, we consider agents that evaluate their location by the average type-difference or the maximum type-difference to their neighbors, or by having a certain tolerance range for type-values of neighboring agents. We study the existence and computation of equilibria and provide bounds on the Price of Anarchy and Stability. Also, we present simulation results that compare our models and shed light on the obtained equilibria for our variants.

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].

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.

TCS Journal 2022 Journal Article

On the robustness of the approximate price of anarchy in generalized congestion games

• Vittorio Bilò

One of the main results shown through Roughgarden's notions of smooth games and Robust Price of Anarchy is that, for any sum-bounded utilitarian social function, the worst-case Price of Anarchy of Coarse Correlated Equilibria coincides with that of Pure Nash Equilibria in the class of weighted congestion games with non-negative and non-decreasing latency functions and that such a value can always be derived through the, so called, smoothness argument. We significantly extend this result by proving that, for a variety of (even non-sum-bounded) utilitarian and egalitarian social functions, and for a broad generalization of the class of weighted congestion games with non-negative (and possibly decreasing) latency functions, the worst-case Price of Anarchy of ϵ-approximate Coarse Correlated Equilibria still coincides with that of ϵ-approximate Pure Nash Equilibria, for any ϵ ≥ 0. As a byproduct of our proof, it also follows that such a value can always be determined by making use of the primal-dual method we introduced in a previous work.

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.

IJCAI Conference 2022 Conference Paper

Tolerance is Necessary for Stability: Single-Peaked Swap Schelling Games

• Davide Bilò
• Vittorio Bilò
• Pascal Lenzner
• Louise Molitor

Residential segregation in metropolitan areas is a phenomenon that can be observed all over the world. Recently, this was investigated via game-theoretic models. There, selfish agents of two types are equipped with a monotone utility function that ensures higher utility if an agent has more same-type neighbors. The agents strategically choose their location on a given graph that serves as residential area to maximize their utility. However, sociological polls suggest that real-world agents are actually favoring mixed-type neighborhoods, and hence should be modeled via non-monotone utility functions. To address this, we study Swap Schelling Games with single-peaked utility functions. Our main finding is that tolerance, i. e. , agents favoring fifty-fifty neighborhoods or being in the minority, is necessary for equilibrium existence on almost regular or bipartite graphs. Regarding the quality of equilibria, we derive (almost) tight bounds on the Price of Anarchy and the Price of Stability. In particular, we show that the latter is constant on bipartite and almost regular graphs.

JAAMAS Journal 2022 Journal Article

Topological influence and locality in swap schelling games

• Davide Bilò
• Vittorio Bilò
• Louise Molitor

Abstract Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i. e. , if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling’s model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i. e. , if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.

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.

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.

MFCS Conference 2020 Conference Paper

Topological Influence and Locality in Swap Schelling Games

• Davide Bilò
• Vittorio Bilò
• Pascal Lenzner
• Louise Molitor

Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i. e. , if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling’s model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i. e. , if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.

TCS Journal 2019 Journal Article

Editorial

• Vittorio Bilò
• Antonio Caruso

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.

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.

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.

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.

TCS Journal 2017 Journal Article

Approximating the revenue maximization problem with sharp demands

• Vittorio Bilò
• Michele Flammini
• Gianpiero Monaco

We consider the revenue maximization problem with sharp multi-demand, in which m indivisible items have to be sold to n potential buyers. Each buyer i is interested in getting exactly d i items, and each item j gives a benefit v i j to buyer i. In particular, each item j has a quality q j, each buyer i has a value v i and the benefit v i j is defined as the product v i q j. The problem asks to determine a price for each item and an allocation of bundles of items to buyers with the aim of maximizing the total revenue, i. e. , the sum of the prices of all the sold items. The allocation must be envy-free, that is, each buyer must be happy with her assigned bundle and cannot improve her utility, defined as the benefit of all the items in the bundle minus their purchase prices, by receiving any different bundle. We first prove that the problem cannot be approximated within a factor of O ( m 1 − ϵ ), for any ϵ > 0, unless P = NP and that this result is asymptotically tight. In fact, we show that a simple greedy algorithm provides an m-approximation of the optimal revenue (this approximation guarantee holds even for the generalization in which the benefits v i j are completely arbitrary). Then, we focus on an interesting subclass of “proper” instances, i. e. , not containing buyers (useless buyers) who are a priori known to be not able to receive any bundle. For these instances, we design an interesting 2-approximation algorithm and show that no better approximation is possible unless P = NP. We stress that it is possible to efficiently check if an instance is proper and, if discarding useless buyers is allowed, an instance can be made proper in polynomial time without worsening the value of its optimal solution.

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.

TCS Journal 2013 Journal Article

Social context congestion games

• Vittorio Bilò
• Alessandro Celi
• Michele Flammini
• Vasco Gallotti

We consider the social context games introduced by Ashlagi et al. (2008) [2], where we are given a classical game, an undirected social context graph expressing collaboration among the players and an aggregation function. The players and strategies are as in the underlying game, while the players’ costs are computed from their immediate costs, that is the original payoffs in the underlying game, according to the neighborhood in the social context graph and the aggregation function. More precisely, the perceived cost incurred by a player is the result of the aggregation function applied to the immediate costs of her neighbors and of the player herself. We investigate social context games in which the underlying games are linear congestion games and Shapley cost sharing games, while the aggregation functions are min, max and sum. In each of the six arising cases, we first completely characterize the class of the social context graph topologies guaranteeing the existence of pure Nash equilibria. We then provide optimal or asymptotically optimal bounds on the price of anarchy of 22 out of the 24 cases obtained by considering four social cost functions, namely, max and sum of the players’ immediate and perceived costs. Finally, we extend some of our results to multicast games, a relevant subclass of the Shapley cost sharing ones.

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*.

TCS Journal 2011 Journal Article

Extending the notion of rationality of selfish agents: Second Order Nash equilibria

• Vittorio Bilò
• Michele Flammini

Motivated by the increasing interest of the Computer Science community in the study and understanding of non-cooperative systems, we present a novel model for formalizing the rational behavior of agents with a more farsighted view of the consequences of their actions. This approach yields a framework creating new equilibria, which we call Second Order equilibria, starting from a ground set of traditional ones. By applying our approach to pure Nash equilibria, we define the set of Second Order pure Nash equilibria and present their applications to the Prisoner’s Dilemma game, to an instance of Braess’s Paradox in the W a r d r o p model and to the K P model with identical machines.

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.

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.

MFCS Conference 2007 Conference Paper

Extending the Notion of Rationality of Selfish Agents: Second Order Nash Equilibria

• Vittorio Bilò
• Michele Flammini

Abstract Motivated by the increasing interest of the Computer Science community in the study and understanding of non-cooperative systems, we present a novel model for formalizing the rational behavior of agents with a more farsighted view of the consequences of their actions. This approach yields a framework creating new equilibria, which we call Second Order equilibria, starting from a ground set of traditional ones. By applying our approach to pure Nash equilibria, we define the set of Second Order Nash equilibria and present their applications to the Prisoner’s Dilemma game, to an instance of Braess’s Paradox in the W ardrop model and to the KP model with identical machines.