Supervisor

Suitable for

Abstract

Coalitions and coalition formation are central concerns in the study of multiagent systems as well as cooperative game theory. Typical real-world examples include individuals joining clubs or societies such as music groups or sport teams, task allocation, or students living in shared housing. The formal study of coalition formation is often realized using so-called hedonic games, which originate from economic theory and focus on coalition structures (or partitions) that satisfy various desiderata based on the agents’ preferences over coalitions. One such desideratum is the notion of popularity:A coalition structure S is said to be popular if, for every other coalition structure S', the number of agents preferring S to S' is larger than the number of agents preferring S' to S. In other words, a popular state is a status quo that cannot be replaced by proposing a different solution that wins a majority vote against the status quo. Popular coalition structures seem to be desirable, but, unfortunately, there exist hedonic games, for which popular outcomes do not exist.

The concept of popularity gives rise to various interesting computational problems, most importantly the existence problem: given a hedonic game, does it contain a popular coalition structure? Two important classes of hedonic games are additively separable hedonic games and fractional hedonic games. For these classes of games, it is known that the existence problem is NP-hard and coNP-hard. However, the best known upper bound is that this problem is contained in Sigma_2^p and it is conjectured that the problem is, in fact, Sigma_2^p-complete. The primary goal of the project is to work on this conjecture. Other possible directions of the project are to consider popularity in restricted classes of hedonic games or to consider related solution concepts, such as strong popularity, mixed popularity, or joint-majority stability.