Fractional hedonic games

Journal article

The work we present in this article initiated the formal study of fractional hedonic games (FHGs), coalition formation games in which the utility of a player is the average value he ascribes to the members of his coalition. Among other settings, this covers situations in which players only distinguish between friends and non-friends and desire to be in a coalition in which the fraction of friends is maximal. FHGs thus not only constitute a natural class of succinctly representable coalition formation games but also provide an interesting framework for network clustering. We propose a number of conditions under which the core of FHGs is nonempty and provide algorithms for computing a core stable outcome. By contrast, we show that the core may be empty in other cases, and that it is computationally hard in general to decide non-emptiness of the core.

Authors: Aziz, H; Brandl, F; Brandt, F; Harrenstein, P; Olsen, M

• Publication status: Accepted
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery (ACM)
• Journal: ACM Transactions on Economics and Computation (TEAC)
• Volume: 7
• Issue: 2
• Article number: 6
• Publication date: 2019-08-01
• Acceptance date: 2019-02-15
• DOI: 10.1145/3327970
• EISSN: 2167-8383
• ISSN: 2167-8375
• Keywords: FFR