Coalition Structure Generation for Partition Function Games Utilizing a Concise Graphical Representation

被引：3

作者：

Zha, Aolong ^{[1
]}

Nomoto, Kazuki ^{[1
]}

Ueda, Suguru ^{[2
]}

Koshimura, Miyuki ^{[1
]}

Sakurai, Yuko ^{[3
]}

Yokoo, Makoto ^{[1
]}

机构：

[1] Kyushu Univ, Fukuoka, Japan

[2] Saga Univ, Saga, Japan

[3] Natl Inst Adv Ind Sci & Technol, Tokyo, Japan

来源：

PRINCIPLES AND PRACTICE OF MULTI-AGENT SYSTEMS (PRIMA 2017) | 2017年 / 10621卷

关键词：

Coalition structure generation; Partition function game; Depth-first branch-and-bound; Maximum satisfiability; MAXSAT;

D O I：

10.1007/978-3-319-69131-2_9

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Coalition Structure Generation (CSG), a main research issue in the domain of coalition games, involves partitioning agents into exhaustive and disjoint coalitions to optimize the social welfare. The advent of compact representation schemes, such as Partition Decision Trees (PDTs), promotes the efficiency of solving CSG problems. This paper studies the CSG problem for partition function games (PFGs) which are coalitional games with externalities. In PFGs, each value of a coalition depends on how the other agents are partitioned. We apply PDTs to represent PFGs and present two methods to solve CSG problems: a depth-first branch-and-bound algorithm and MaxSAT encoding.

引用

页码：143 / 159

页数：17

共 19 条

[1]

Chalkiadakis G., 2011, Computational Aspects of Cooperative Game Theory

[2]

Cook S. A., 1971, Proceedings of the 3rd annual ACM symposium on theory of computing, P151

[3]

Dang V.D., 2006, 21st National Conference on AI, P635

[4]

Ieong S., 2005, P 6 ACM C EL COMM, P193, DOI DOI 10.1145/1064009.1064030

[5]

Koshimura M., 2012, Journal on Satisfiability, Boolean Modeling and Computation, V8, P95

[6] MaxSAT, hard and soft constraints [J].

Front. Artif. Intell. Appl., 2009, 1 (613-631) :613-631

[7] Extending MaxSAT to Solve the Coalition Structure Generation Problem with Externalities Based on Agent Relations [J].

Liao, Xiaojuan ;

Koshimura, Miyuki ;

Fujita, Hiroshi ;

Hasegawa, Ryuzo .

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2014, E97D (07) :1812-1821

[8] MaxSAT Encoding for MC-Net-Based Coalition Structure Generation Problem with Externalities [J].

Liao, Xiaojuan ;

Koshimura, Miyuki ;

Fujita, Hiroshi ;

Hasegawa, Ryuzo .

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2014, E97D (07) :1781-1789

[9] Solving the Coalition Structure Generation Problem with MaxSAT [J].

Liao, Xiaojuan ;

Koshimura, Miyuki ;

Fujita, Hiroshi ;

Hasegawa, Ryuzo .

2012 IEEE 24TH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI 2012), VOL 1, 2012, :910-915

[10]

Michalak T., 2010, Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, P125

← 1 2 →