Fractional hedonic games

Haris Aziz; Florian Brandl; Felix Brandt; Paul Harrenstein; Martin Olsen; Dominik Peters

doi:10.1145/3327970

Fractional hedonic games

Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, Dominik Peters

Department of Business Development and Technology

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

80 Citations (Scopus)

Abstract

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.

Original language	English
Article number	a6
Journal	ACM Transactions on Economics and Computation
Volume	7
Issue	2
ISSN	2167-8375
DOIs	https://doi.org/10.1145/3327970
Publication status	Published - Jun 2019

Keywords

Coalition formation
Cooperative game theory
Core
Hedonic games

Access to Document

10.1145/3327970

https://arxiv.org/pdf/1705.10116.pdf

Cite this

@article{fcb8c82401a147bf8a8eea5a70d14eea,

title = "Fractional hedonic games",

abstract = "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.",

keywords = "Coalition formation, Cooperative game theory, Core, Hedonic games",

author = "Haris Aziz and Florian Brandl and Felix Brandt and Paul Harrenstein and Martin Olsen and Dominik Peters",

year = "2019",

month = jun,

doi = "10.1145/3327970",

language = "English",

volume = "7",

journal = "ACM Transactions on Economics and Computation",

issn = "2167-8375",

publisher = "Association for Computing Machinery",

number = "2",

}

TY - JOUR

T1 - Fractional hedonic games

AU - Aziz, Haris

AU - Brandl, Florian

AU - Brandt, Felix

AU - Harrenstein, Paul

AU - Olsen, Martin

AU - Peters, Dominik

PY - 2019/6

Y1 - 2019/6

N2 - 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.

AB - 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.

KW - Coalition formation

KW - Cooperative game theory

KW - Core

KW - Hedonic games

UR - http://www.scopus.com/inward/record.url?scp=85067245837&partnerID=8YFLogxK

U2 - 10.1145/3327970

DO - 10.1145/3327970

M3 - Journal article

AN - SCOPUS:85067245837

SN - 2167-8375

VL - 7

JO - ACM Transactions on Economics and Computation

JF - ACM Transactions on Economics and Computation

IS - 2

M1 - a6

ER -

Fractional hedonic games

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this