Aarhus University Seal

Distance Hedonic Games

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearch

  • Michele Flammini, Gran Sasso Science Institute, Italy
  • Bojana Kodric, Gran Sasso Science Institute, Italy
  • Martin Olsen
  • Giovanna Varricchio, Gran Sasso Science Institute, Italy

In this paper we consider Distance Hedonic Games (DHGs), a class of non-transferable utility coalition formation games that properly generalizes previously existing models, like Social Distance Games (SDGs) and unweighted Fractional Hedonic Games (FHGs). In particular, in DHGs we assume the existence of a scoring vector α, in which the i-th coefficient α i expresses the extent to which an agent x contributes to the utility of an agent y if they are at distance i. We focus on Nash stable outcomes in the arising games, i.e., on coalition structures in which no agent can unilaterally improve her gain by deviating. We consider two different natural scenarios for the scoring vector, with monotonically increasing and monotonically decreasing coefficients. In both cases we give NP-hardness and inapproximability results on the problems of finding a social optimum and a best Nash stable outcome. Moreover, we characterize the topologies of coalitions that provide high social welfare and consequently give suitable bounds on the Price of Anarchy and on the Price of Stability.

Original languageEnglish
Title of host publicationSOFSEM 2021 : Theory and Practice of Computer Science - 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Proceedings
Number of pages16
PublisherSpringer
Publication year2021
Pages159-174
ISBN (print)978-3-030-67730-5
ISBN (Electronic)978-3-030-67731-2
DOIs
Publication statusPublished - 2021
EventInternational Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021 - Bolzano-Bozen, Italy
Duration: 25 Jan 202129 Jan 2021
Conference number: 47th

Conference

ConferenceInternational Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021
Nummer47th
LandItaly
ByBolzano-Bozen
Periode25/01/202129/01/2021
SeriesLecture Notes in Computer Science (LNCS)
Volume12607
ISSN0302-9743

    Research areas

  • Coalition formation, Hedonic Games, Nash stability

See relations at Aarhus University Citationformats

ID: 212248304