Robustness against Agent Failure in Hedonic Games

Robustness against Agent Failure in Hedonic Games

Ayumi Igarashi, Kazunori Ota, Yuko Sakurai, Makoto Yokoo

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 364-370. https://doi.org/10.24963/ijcai.2019/52

We study how stability can be maintained even after any set of at most k players leave their groups, in the context of hedonic games. While stability properties ensure an outcome to be robust against players' deviations, it has not been considered how an unexpected change caused by a sudden deletion of players affects stable outcomes. In this paper we propose a novel criterion that reshapes stability form robustness aspect. We observe that some stability properties can be no longer preserved even when a single agent is removed. However, we obtain positive results by focusing on symmetric friend-oriented hedonic games. We prove that we can efficiently decide the existence of robust outcomes with respect to Nash stability underdeletion of any number of players or contractual individual stability under deletion of a single player. We also prove that symmetric additively separable games always admit an individual stable outcome that is robust with respect to individual rationality.
Keywords:
Agent-based and Multi-agent Systems: Cooperative Games
Agent-based and Multi-agent Systems: Algorithmic Game Theory