An Introduction to Compatibility Game

The problem with which we shall be concerned relates to the following typical situation: We have a finite set of individuals who must be divided into teams to carry out a certain number of tasks. However, due to issues related to temperament or ego, or even professional rivalry, some of these individuals cannot be part of the same work team. How to distribute them satisfactorily? We answer this question by introducing the compatibility game [Formula: see text], which consists of a set [Formula: see text] of individuals and a map [Formula: see text] from [Formula: see text] to [Formula: see text] such that for all [Formula: see text], [Formula: see text]. Using this compatibility game, we define its compatibility graph [Formula: see text]. We prove that a solution to the given problem is a clique-partition of the compatibility graph [Formula: see text]. We conclude our paper with a necessary and sufficient condition for a compatibility game to admit solutions and a mechanism for determining all solutions.