The complexity of verifying popularity and strict popularity in altruistic hedonic games
Autonomous Agents and Multi-Agent Systems · 2024-12 · 38 (2)
DOI: 10.1007/s10458-024-09679-0 ↗Kurz gefasst
Fachartikel in der Zeitschrift Autonomous Agents and Multi-Agent Systems, online erschienen am 01.10.2024. Verfasst von Anna Maria Kerkmann und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NRW project "Online Participation", Deutsche Forschungsgemeinschaft, Heinrich-Heine-Universität Düsseldorf.
Abstract (Originalsprache)
We consider average- and min-based altruistic hedonic games and study the problem of verifying popular and strictly popular coalition structures. While strict popularity verification has been shown to be coNP-complete in min-based altruistic hedonic games, this problem has been open for equal- and altruistic-treatment average-based altruistic hedonic games. We solve these two open cases of strict popularity verification and then provide the first complexity results for popularity verification in (average- and min-based) altruistic hedonic games, where we cover all three degrees of altruism.
Förderung
- NRW project "Online Participation"
- Deutsche Forschungsgemeinschaft
- Heinrich-Heine-Universität Düsseldorf
Zitieren
APA
Kerkmann, A. M., & Rothe, J. (2024). The complexity of verifying popularity and strict popularity in altruistic hedonic games. Autonomous Agents and Multi-Agent Systems, 38(2). https://doi.org/10.1007/s10458-024-09679-0
Vancouver
Kerkmann AM, Rothe J. The complexity of verifying popularity and strict popularity in altruistic hedonic games. Autonomous Agents and Multi-Agent Systems. 2024;38(2). doi:10.1007/s10458-024-09679-0
BibTeX
@article{Kerkmann2024,
author = {Kerkmann, Anna Maria and Rothe, Jörg},
title = {The complexity of verifying popularity and strict popularity in altruistic hedonic games},
journal = {Autonomous Agents and Multi-Agent Systems},
year = {2024},
volume = {38},
number = {2},
doi = {10.1007/s10458-024-09679-0}
}
EUVIMED