23 April 2018, ILLC Seminar, Anja Rey

Coalition formation games model situations in which agents cooperate in teams, such as stable-roommate problems and project allocation problems, based on individual preferences of the agents. Questions of interests are related to stable and fair outcomes as well as representations of these games.

In this talk, firstly, an overview of hedonic games is given. These
can model agents' preferences over coalitions (i.e. sets of agents),
where the happiness of agents with a coalition structure only depends on their own coalition. Within the recent twenty years, various representations and stability notions, such as Nash stability, havebeen studied. Trade-offs exist between compact encodings and expressivity as well as the computational complexity of stability problems.

Secondly, a model of hedonic games with ordinal preferences and
thresholds is presented. Here, it is assumed that agents only know
a subset of their co-agents whom they partition into the sets of
friends and enemies. The remaining agents are considered as
neutral. At the same time they specify a weak order over the former
two sets. This relation is extended to a set of possible
preferences over coalitions such that it is reasonable to define
the notions of possible and necessary stability. While this model
can express preferences more generally than related models, the
complexity of various stability problems does not increase. Nevertheless many of these problems remain NP-hard or
even hard for the second level of the polynomial hierarchy.

In the literature natural restrictions are known that allow a decision
of some stability problems. Nevertheless, in order to evaluate
the stability of, e.g., a distribution into working groups, the
whole game has to be taken into consideration. In particular, in
large institutions or social networks, it would be desirable to
deduce global information from local samples.  Finally, in this
talk an initial result to tackle this problem with property
testing in the context of hedonic games is introduced.