Existence, Computation and Efficiency of Nash Stable Outcomes in Hedonic Skill Games

Abstract

This article deals with hedonic skill games, a non-transferable utility counterpart of coalitional skill games which model collaboration among entities through the abstract notions of tasks and the skills required to complete them. In the weighted tasks setting, we show that deciding whether an instance of the game admits a Nash stable outcome is NP-complete. We then characterize the instances admitting a Nash stable outcome. This characterization relies on the fact that every agent holds (resp., every task requires) either a single skill or more than one skill. For these instances, the complexity of computing a Nash stable outcome is determined, together with the possibility that natural dynamics converge to a Nash stable outcome from any initial configuration. Our study is completed with a thorough analysis of the price of anarchy of instances always admitting a Nash stable outcome.