Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

23 April 2018, ILLC Seminar, Anja Rey

Speaker: Anja Rey
Title: Testing Stability Properties in Graphical Hedonic Games
Date: Monday 23 April 2018
Time: 14:00-14:50
Location: ILLC Seminar Room F1.15, Science Park 107, Amsterdam

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.

For more information, contact Yde Venema at .

Please note that this newsitem has been archived, and may contain outdated information or links.