Distance hedonic games
| Autor: | Bojana Kodric, Martin Olsen, Michele Flammini, Giovanna Varricchio |
|---|---|
| Předmět: |
Computer Science::Computer Science and Game Theory
Class (set theory) Computer science Social distance Social Welfare Monotonic function 0102 computer and information sciences 02 engineering and technology 01 natural sciences Outcome (game theory) 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Price of anarchy 020201 artificial intelligence & image processing Price of stability Mathematical economics |
| Zdroj: | Scopus-Elsevier Aarhus University Flammini, M, Kodric, B, Olsen, M & Varricchio, G 2021, Distance Hedonic Games . in SOFSEM 2021 : Theory and Practice of Computer Science . Springer, Lecture Notes in Computer Science (LNCS), vol. 12607, pp. 159-174, International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Bolzano-Bozen, Italy, 25/01/2021 . https://doi.org/10.1007/978-3-030-67731-2_12 SOFSEM 2021: Theory and Practice of Computer Science ISBN: 9783030677305 SOFSEM Flammini, M, Kodric, B, Olsen, M & Varricchio, G 2020, Distance Hedonic Games . in AAMAS 2020, May 9–13, Auckland, New Zealand . IFAAMAS, AAMAS 2020, Auckland, New Zealand, 09/05/2020 . < http://ifaamas.org/Proceedings/aamas2020/ > |
| DOI: | 10.1007/978-3-030-67731-2_12 |
| Popis: | In this paper we consider Distance Hedonic Games, a class of non-transferable utility coalition formation games that properly generalizes previously existing models, like Social Distance Games and Fractional Hedonic Games. In particular, in Distance Hedonic Games we assume the existence of a scoring vector α, in which the i-th coefficient αi expresses the extent to which x contributes to the utility of y if they are at distance i. We focus on Nash stable outcomes and consider two natural scenarios for the scoring vector: monotonically decreasing and monotonically increasing coefficients. In both cases we give NP-hardness and inapproximability results for the problems of finding a social optimum and a best Nash stable outcome. Moreover, we characterize the topologies of coalitions with high social welfare and give bounds on the Price of Anarchy and on the Price of Stability. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|