Solving Four Open Problems about Core Stability in Altruistic Hedonic Games

Rothe, J and Schlotter, Ildikó Anna (2025) Solving Four Open Problems about Core Stability in Altruistic Hedonic Games. ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 437. pp. 15-29. ISSN 2075-2180

Preview

Text 2511.22370v1.pdf - Draft Version Available under License Creative Commons Attribution. Download (208kB) | Preview

Abstract

Hedonic games—at the interface of cooperative game theory and computational social choice—are coalition formation games in which the players have preferences over the coalitions they can join. Kerkmann et al. [13] introduced altruistic hedonic games where the players’ utilities depend not only on their own but also on their friends’ valuations of coalitions. The complexity of the verification problem for core stability has remained open in four variants of altruistic hedonic games: namely, for the variants with average- and minimum-based “equal-treatment” and “altruistic-treatment” preferences. We solve these four open questions by proving the corresponding problems coNP-complete; our reductions rely on rather intricate gadgets in the related networks of friends.

Actions (login required)

Edit Item