Computational Complexity of Hedonic Games on Sparse Graphs

被引：2

作者：

Hanaka, Tesshu ^{[1
]}

Kiya, Hironori ^{[2
]}

Maei, Yasuhide ^{[2
]}

Ono, Hirotaka ^{[2
]}

机构：

[1] Chuo Univ, Dept Informat & Syst Engn, Bunkyo Ku, 1-13-27 Kasuga, Tokyo, Japan

[2] Nagoya Univ, Grad Sch Informat, Chikusa Ku, Furo Cho, Nagoya, Aichi, Japan

来源：

PRINCIPLES AND PRACTICE OF MULTI-AGENT SYSTEMS (PRIMA 2019) | 2019年 / 11873卷

关键词：

Hedonic games; Coalition formation; Social network; PLS-completeness; Parameterized algorithm; STABILITY;

D O I：

10.1007/978-3-030-33792-6_43

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The additively separable hedonic game (ASHG) is a model of coalition formation games on graphs. In this paper, we intensively and extensively investigate the computational complexity of finding several desirable solutions, such as a Nash stable solution, a maximum utilitarian solution, and a maximum egalitarian solution in ASHGs on sparse graphs including bounded-degree graphs, bounded-treewidth graphs, and nearplanar graphs. For example, we show that finding a maximum egalitarian solution is weakly NP-hard even on graphs of treewidth 2, whereas it can be solvable in polynomial time on trees. Moreover, we give a pseudo fixed parameter algorithm when parameterized by treewidth.

引用

页码：576 / 584

页数：9

共 19 条

[1] Tree-like structure in large social and information networks [J].

Adcock, Aaron B. ;

Sullivan, Blair D. ;

Mahoney, Michael W. .

2013 IEEE 13TH INTERNATIONAL CONFERENCE ON DATA MINING (ICDM), 2013, :1-10

[2] Researching with whom? Stability and manipulation [J].

Alcalde, J ;

Revilla, P .

JOURNAL OF MATHEMATICAL ECONOMICS, 2004, 40 (08) :869-887

[3]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[4] Computing desirable partitions in additively separable hedonic games [J].

Aziz, Hans ;

Brandt, Felix ;

Seedig, Hans Georg .

ARTIFICIAL INTELLIGENCE, 2013, 195 :316-334

[5]

Aziz H, 2014, AAMAS'14: PROCEEDINGS OF THE 2014 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS, P5

[6] NP-completeness in hedonic games [J].

Ballester, C .

GAMES AND ECONOMIC BEHAVIOR, 2004, 49 (01) :1-30

[7] Core in a simple coalition formation game [J].

Banerjee, S ;

Konishi, H ;

Sönmez, T .

SOCIAL CHOICE AND WELFARE, 2001, 18 (01) :135-153

[8] The stability of hedonic coalition structures [J].

Bogomolnaia, A ;

Jackson, MO .

GAMES AND ECONOMIC BEHAVIOR, 2002, 38 (02) :201-230

[9]

Cygan M., 2015, PARAMETERIZED, V4, DOI [10.1007/978-3-319-21275-3, DOI 10.1007/978-3-319-21275-3]

[10] HEDONIC COALITIONS - OPTIMALITY AND STABILITY [J].

DREZE, JH ;

GREENBERG, J .

ECONOMETRICA, 1980, 48 (04) :987-1003

← 1 2 →