1,721,040 research outputs found
The impact of selfishness in hypergraph hedonic games
No full textWe 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 defined 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
The price of stability for undirected broadcast network design with fair cost allocation is constant
No full textWe 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 Anshelevich et al. (2008). 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⁎
Generalized Distance Polymatrix Games
No full textWe consider a generalization of the distance polymatrix coordination games to hypergraphs. The classic polymatrix coordination games and the successive distance polymatrix coordination games are usually modelled by means of undirected graphs, where nodes represent agents, and edges stand for binary games played by the agents at their extremes. The utility of an agent depends at different scales on the outcome of a suitably defined subset of all binary games, plus the preference she has for her action. We propose the new class of generalized distance polymatrix games, properly generalizing distance polymatrix coordination games, in which each subgame can be played by more than two agents. They can be suitably modelled by means of hypergraphs, where each hyperedge represents a subgame played by its agents. Moreover, as for distance polymatrix coordination games, the overall utility of a player x also depends on the payoffs of the subgames where the involved players are far, at most, a given distance from x. As for the original model, we discount these payoffs proportionally by factors depending on the distance of the related hyperedges. After formalizing and motivating our model, we first investigate the existence of exact and approximate strong equilibria. Then we study the degradation of the social welfare by resorting to the standard measures of Price of Anarchy and Price of Stability, both for general and bounded-degree graphs
Strategyproof mechanisms for Friends and Enemies Games
No full textWe investigate strategyproof mechanisms for Friends and Enemies Games, a subclass of Hedonic Games in which every agent classifies any other one as a friend or as an enemy. In this setting, we consider the two classical scenarios proposed in the literature, called Friends Appreciation (FA) and Enemies Aversion (EA). Roughly speaking, in the former each agent gives priority to the number of friends in her coalition, while in the latter to the number of enemies. We focus on the objective of maximizing the sum of the utilities of the agents and provide strategyproof mechanisms for both settings. More precisely, for FA we first present a deterministic n-approximation mechanism, n being the number of agents, and then show that a much better approximation can be achieved by resorting to randomization. Namely, we provide a randomized mechanism whose expected approximation ratio is 4, and arbitrarily close to 4 with high probability. For EA, we give a simple (1+2)n-approximation mechanism, and show that its performance is asymptotically tight by proving that it is NP-hard to approximate the optimal solution within O(n1−ε) for any fixed ε>0. We also show that, if computational efficiency is not a concern, it is possible to achieve a (1+2)-approximation by means of a deterministic strategyproof mechanism with exponential runtime. Finally, we show how to extend our results in the presence of neutrals, i.e., when agents can also be indifferent about other agents
On nash equilibria in non-cooperative all-optical networks
Full text linkWe consider the problem of determining a routing in all-optical networks, in which some couples of nodes want to communicate. In particular, we study this problem from the point of view of a network provider that has to design suitable payment functions for non-cooperative agents, corresponding to the couples of nodes wishing to communicate. The network provider aims at inducing stable routings (i.e., routings corresponding to Nash equilibria) using a low number of wavelengths. We consider three different kinds of local knowledge that agents may exploit to compute their payments, leading to three corresponding information levels. Under complete information, the network provider can design a payment function, inducing the agents to reach a Nash equilibrium mirroring any desired routing. If the price to an agent is computed only as a function of the wavelengths used along connecting paths (minimal level) or edges (intermediate level), the most reasonable functions either do not admit Nash equilibria or admit very inefficient ones, i.e., with the largest possible price of anarchy. However, by suitably restricting the network topology, a constant price of anarchy for chains and rings and a logarithmic one for trees can be obtained under the minimal and intermediate levels, respectively
- …
