Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/2671
Title: On Hedonic Games with Common Ranking Property
Authors: Çaşkurlu, Buğra
Kızılkaya, Fatih Erdem
Keywords: Algorithmic game theory
computational complexity
hedonic games
pareto optimality
core stability
Issue Date: 2019
Publisher: Springer Verlag
Source: Caskurlu, B., and Kizilkaya, F. E. (2019, May). On Hedonic Games with Common Ranking Property. In International Conference on Algorithms and Complexity (pp. 137-148). Springer, Cham.
Abstract: Hedonic games are a prominent model of coalition formation, in which each agent’s utility only depends on the coalition she resides. The subclass of hedonic games that models the formation of general partnerships [21], where output is shared equally among affiliates, is called hedonic games with common ranking property (HGCRP). Aside from their economic motivation, HGCRP came into prominence since they are guaranteed to have core stable solutions that can be found efficiently [2]. Nonetheless, a core stable solution is not necessarily a socially desirable (Pareto optimal) outcome. We improve upon existing results by proving that every instance of HGCRP has a solution that is both Pareto optimal and core stable. We establish that finding such a solution is, however, - by proving the stronger statement that finding any Pareto optimal solution is. We show that the gap between the total utility of a core stable solution and that of the socially optimal solution (OPT) is bounded by |N|, where N is the set of agents, and that this bound is tight. Our investigations reveal that finding a solution, whose total utility is within a constant factor of that of OPT, is intractable. © 2019, Springer Nature Switzerland AG.
Description: 11th International Conference on Algorithms and Complexity ( 2019: Rome; Italy )
URI: https://link.springer.com/chapter/10.1007%2F978-3-030-17402-6_12
https://hdl.handle.net/20.500.11851/2671
ISBN:  9783030174019
ISSN: 3029743
Appears in Collections:Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection

Show full item record

CORE Recommender

Page view(s)

22
checked on Dec 26, 2022

Google ScholarTM

Check

Altmetric


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.