# Robustness against Agent Failure in Hedonic Games

arXiv: https://arxiv.org/abs/1903.05534 · HTML: https://mlsanity.com/paper/1903.05534/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2019.

## Built on by (most cited first, 1 of 1)

- [Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size](https://mlsanity.com/paper/2505.22384/) (2025)

## Abstract (arXiv)

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 under deletion of any number of players or contractual individual stability under deletion of a single player. We also show that symmetric additively separable games always admit an individual stable outcome that is robust with respect to individual rationality.