Efficient computation of hedonic games for AI

Short description

How do you make a group of autonomous intelligent robots collaborate effectively in order to carry out a particular task? The theory of hedonic games provides a foundation for such questions.

About the project

The M.Sc. course in Computer Vision and Artificial Intelligence started in the summer semester 2022 and this project – which was jointly supervised by Jochen Staudacher from Kempten and Stefano Moretti from Université Paris-Dauphine – was the second international student project in that program.
A hedonic game [1] [2] (sometimes also referred to as a hedonic coalition formation game) is aspecial type of non-transferable utility game. It aims to model the formation of coalitions of players when players have individual preferences over which group they belong to. A hedonic game is specified by
a) a finite set of players and,

b) a preference ranking over all coalitions for each individual player specifying the preference of a player for all the coalitions he belongs to.

Hedonic games lead to computationally challenging questions [3].

The purpose of this project was to develop a prototypical R package for general hedonic games in the same fashion as the established package CoopGame [4] for cooperative games with transferable utility.

We are striving to establish our R package HedonicGames as an official extension of the R ecosystem. We are confident that it will be helpful in furthering the collaboration between Université Paris-Dauphine and Kempten University as well as useful to researchers worldwide.

Authors

Kempten students taking part in the project: Fabian Gumpp, Daniel McGee, Felix Wagner.

Supervisors: Jochen Staudacher (Kempten), Stefano Moretti (Université Paris-Dauphine)

Faculty: Computer Science, M.Sc. Program in Computer Vision and Artificial Intelligence

Date of realisation: SS 2023

References

[1] A. Bogomolnaia, M.O. Jackson, The Stability of Hedonic Coalition Structures. Games and Economic
Behavior, 38 (2), 201–230, 2002.
​
[2] H. Aziz, R. Savani, Hedonic Games. Chapter 15 (pp. 356-376) in: Brandt, F.; Conitzer, V.; Endriss,

U.; Lang, J.; Procaccia, A. D. (2016). Handbook of Computational Social Choice. Cambridge University Press.

[3] C. Ballester, NP-completeness in hedonic games, Games and Economic Behavior. 49 (1), 1–30, 2004.

[4] J. Staudacher, J. Anwander, Using the R package CoopGame for the analysis, solution and visualization of cooperative games with transferable utility. R Vignette for package version 0.2.2, 2022, https://cran.r-project.org/package=CoopGame