Maximizing Social Welfare in Score-Based Social Distance Games
Electronic Proceedings in Theoretical Computer Science · 11.07.2023 · 379 · 272-286
DOI: 10.4204/eptcs.379.22 ↗Kurz gefasst
Fachartikel in der Zeitschrift Electronic Proceedings in Theoretical Computer Science, online erschienen am 11.07.2023. Verfasst von Robert Ganian und 5 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 39 Literaturangaben.
Abstract (Originalsprache)
Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function $u$ that took into account distances in a given social network. In this paper, we consider a non-normalized score-based definition of social distance games where the utility function $u^s$ depends on a generic scoring vector $s$, which may be customized to match the specifics of each individual application scenario. As our main technical contribution, we establish the tractability of computing a welfare-maximizing partitioning of the agents into coalitions on tree-like networks, for every score-based function $u^s$. We provide more efficient algorithms when dealing with specific choices of $u^s$ or simpler networks, and also extend all of these results to computing coalitions that are Nash stable or individually rational. We view these results as a further strong indication of the usefulness of the proposed score-based utility function: even on very simple networks, the problem of computing a welfare-maximizing partitioning into coalitions remains open for the originally considered canonical function $u$.
Zitieren
APA
Ganian, R., Hamm, T., Knop, D., Roy, S., Schierreich, Š., & Suchý, O. (2023). Maximizing Social Welfare in Score-Based Social Distance Games. Electronic Proceedings in Theoretical Computer Science, 379, 272-286. https://doi.org/10.4204/eptcs.379.22
Vancouver
Ganian R, Hamm T, Knop D, Roy S, Schierreich Š, Suchý O. Maximizing Social Welfare in Score-Based Social Distance Games. Electronic Proceedings in Theoretical Computer Science. 2023;379:272-286. doi:10.4204/eptcs.379.22
BibTeX
@article{Ganian2023,
author = {Ganian, Robert and Hamm, Thekla and Knop, Dušan and Roy, Sanjukta and Schierreich, Šimon and Suchý, Ondřej},
title = {Maximizing Social Welfare in Score-Based Social Distance Games},
journal = {Electronic Proceedings in Theoretical Computer Science},
year = {2023},
volume = {379},
pages = {272--286},
doi = {10.4204/eptcs.379.22}
}
EUVIMED