Computational complexity of popularity in hedonic games

This project falls within the EPSRC Artificial intelligence technologies and theoretical computer science research areas.

An important task in the theory of economics, game theory, and machine learning, is the task of partitioning agents (e.g., people, countries, machines etc.) into groups. E.g., in democratic elections political parties form coalitions based on their ability to cooperate; countries reach customs unions agreements by grouping together as collaborating economic units; people are divided into teams for a sports match; and in machine learning data points are being clustered based on shared characteristics.

In these examples we wish to be able to find a division of the agents into groups in a way that considers their relations. However, the number of possible partitions may be huge, making the task of finding a good partition quite hard. The framework of hedonic games captures such scenarios.

In hedonic games agents express their preferences regarding which coalitions they wish to be in. Our goal is then to partition the agents in a way that reflects those

preferences. In this project we focus our attention on a well-studied solution concept called popularity. A partition P is called popular if, when compared with any other partition P', the number of agents who prefer P over P' is at least as much as the converse. It is, arguably, a relatable idea that reflects democratic principles.

While it is natural to assume that we can always find "the most popular" partition, certain instances of this game admit no popular partition. Hence, it is interesting to ask whether we can determine if a popular partition exists, given a hedonic game instance (the popularity existence problem). Specifically, we wish to determine the computational hardness of this problem, by classifying it to its appropriate complexity class.

Informally, this means we seek to understand how well a modern computer would cope with this problem, which is essential to apply theoretical ideas in real life. In various classes of hedonic games, the popularity existence problem has not been solved yet. One aim of this project is to close those gaps by settling the complexity of popularity in those classes.

Another goal is to explore other variations of popularity, such as strong popularity and mixed popularity. While these notions are closely related to popularity in essence, it appears that from a computational complexity perspective they have unique characteristics that separate them from each other. In fact, it seems difficult to find any known problem that shares the same computational complexity as strong or mixed popularity.

The consequences of this are twofold. Firstly, to characterize the complexity of these problems one would need to define new complexity classes and prove that they

capture the essence of the respective problems. This stands in contrast to the usual approach: Typically, one would search for problems with similar nature whose

computational hardness is already established and show computational equivalence between that and the problem at hand. If no such problem exists, this approach fails, thus forcing us to define an appropriate class from scratch. This could provide deeper insights into computational complexity in general, regardless of the game-theoretic nature of our motivating problems. E.g., this may shed light on the structures of complexity classes and the characteristics which affect a problem's nature.

Secondly, defining a complexity class that describes real-life problems may open a gate to understanding other problems as well. Uncovering the unique computational characteristics of those problems could potentially help characterizing a variety of problems from numerous seemingly unrelated fields, such as cryptography, machine learning, or economics, which currently have no accurate hardness classification.