TY - JOUR
AU - Aloisio, Alessandro
AU - Flammini, Michele
AU - Vinci, Cosimo
PY - 2020/04/03
Y2 - 2021/04/14
TI - The Impact of Selfishness in Hypergraph Hedonic Games
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 34
IS - 02
SE - AAAI Technical Track: Game Theory and Economic Paradigms
DO - 10.1609/aaai.v34i02.5542
UR - https://ojs.aaai.org/index.php/AAAI/article/view/5542
SP - 1766-1773
AB - <p>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 <em>hypegraph hedonic game</em> 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 <em><em>k</em>-Nash price of anarchy</em> and <em><em>k</em>-core price of anarchy</em>, where <em>k</em> 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 <em>k</em>, the hypergraph arity <em>r</em> and the number of agents <em>n</em>. 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.</p>
ER -