Hedonic Expertise Games

• Published in: Annals of mathematics and artificial intelligence 2024-06, Vol.92 (3), p.671-690
• Main Authors: Caskurlu, Bugra, Kizilkaya, Fatih Erdem, Ozen, Berkehan
• Format: Article
• Language: English
• Subjects: Approximation; Artificial Intelligence; Complex Systems; Computer Science; Games; Mathematics; Optimization; Polynomials; Ranking; Software development
• ISSN: 1012-2443; 1573-7470
• DOI: 10.1007/s10472-023-09900-y

We introduce a hedonic game form, Hedonic Expertise Games (HEGs), that naturally models a variety of settings where agents with complementary qualities would like to form groups. Students forming groups for class projects, and hackathons in which software developers, graphic designers, project managers, and other domain experts collaborate on software projects, are typical scenarios modeled by HEGs. This game form possesses the common ranking property, and additionally, the coalitional utility function is monotone. We present comprehensive results for the existence/nonexistence of stable and efficient partitions of HEGs with respect to the most common stability and optimality concepts used in the literature. Specifically, we show that an HEG instance may not have a strict core stable partition, and yet every HEG instance has a strong Nash stable and Pareto optimal partition. Furthermore, it may be the case that none of the socially-optimal partitions of an HEG instance is Nash stable or core stable. However, it is guaranteed that every socially-optimal partition is contractually Nash stable. We show that all these existence/nonexistence results also hold for the monotone hedonic games with common ranking property (monotone HGCRP). We also present several results for HEGs from the computational complexity perspective, some of which are as follows: A contractually Nash stable partition (and a Nash stable partition in a restricted setting) can be found in polynomial time. A strong Nash stable partition can be approximated within a factor of 1 - 1 / e , and this bound is tight even for approximating core stable partitions. We present a natural game dynamics for monotone HGCRP that converges to a Nash stable partition in a relatively low number of moves.