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

Institut for Forretningsudvikling og Teknologi

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review

82 Citationer (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.

Originalsprog	Engelsk
Artikelnummer	a6
Tidsskrift	ACM Transactions on Economics and Computation
Vol/bind	7
Nummer	2
ISSN	2167-8375
DOI	https://doi.org/10.1145/3327970
Status	Udgivet - jun. 2019

Adgang til dokumentet

10.1145/3327970

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

Andre filer og links

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

Citationsformater

@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

Adgang til dokumentet

Andre filer og links

Fingeraftryk

Citationsformater