Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research
Final published version
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 language | English |
---|---|
Title of host publication | SOFSEM 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 pages | 16 |
Publisher | Springer |
Publication year | 2021 |
Pages | 159-174 |
ISBN (print) | 978-3-030-67730-5 |
ISBN (Electronic) | 978-3-030-67731-2 |
DOIs | |
Publication status | Published - 2021 |
Event | International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021 - Bolzano-Bozen, Italy Duration: 25 Jan 2021 → 29 Jan 2021 Conference number: 47th |
Conference | International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021 |
---|---|
Nummer | 47th |
Land | Italy |
By | Bolzano-Bozen |
Periode | 25/01/2021 → 29/01/2021 |
Series | Lecture Notes in Computer Science (LNCS) |
---|---|
Volume | 12607 |
ISSN | 0302-9743 |
See relations at Aarhus University Citationformats
ID: 212248304