The Impact of Selfishness in Hypergraph Hedonic Games
| Autor: | Alessandro Aloisio, Michele Flammini, Cosimo Vinci |
|---|---|
| Přispěvatelé: | Aloisio, A., Flammini, M., Vinci, C. |
| Rok vydání: | 2020 |
| Předmět: |
Computer Science::Multiagent Systems
Computer Science::Computer Science and Game Theory Hypergraph Computer science media_common.quotation_subject Price of anarchy Stability (learning theory) Selfishness General Medicine Upper and lower bounds Mathematical economics Outcome (game theory) media_common |
| Zdroj: | AAAI Scopus-Elsevier |
| ISSN: | 2374-3468 2159-5399 |
| DOI: | 10.1609/aaai.v34i02.5542 |
| Popis: | 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 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|