TY - GEN
T1 - Solving Coalition Structure Generation Problems over Weighted Graph
AU - Watanabe, Emi
AU - Koshimura, Miyuki
AU - Sakurai, Yuko
AU - Yokoo, Makoto
N1 - Funding Information:
Acknowledgment. This work was supported by JSPS KAKENHI Grant Numbers JP17H00761, JP17KK0008, JP19H04175, by JST SICORP JPMJSC1607, and by Kayamori Foundation of Informational Science Advancement.
Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - Coalition Structure Generation (CSG), which is a leading research issue in the domain of coalitional games, divides agents into exhaustive and disjoint coalitions to optimize social welfare. This paper studies CSG problems over weighted undirected graphs in which the weight on an edge between any two connecting agents represents how well they work together in a coalition. The weight can have either a positive or a negative value. We examine two types of problems. One is a CSG without any restrictions on the number of coalitions, and another is a CSG with k coalitions where k is determined in advance. We present two methods to solve these problems: ILP formulation and MaxSAT encoding.
AB - Coalition Structure Generation (CSG), which is a leading research issue in the domain of coalitional games, divides agents into exhaustive and disjoint coalitions to optimize social welfare. This paper studies CSG problems over weighted undirected graphs in which the weight on an edge between any two connecting agents represents how well they work together in a coalition. The weight can have either a positive or a negative value. We examine two types of problems. One is a CSG without any restrictions on the number of coalitions, and another is a CSG with k coalitions where k is determined in advance. We present two methods to solve these problems: ILP formulation and MaxSAT encoding.
UR - http://www.scopus.com/inward/record.url?scp=85076421509&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076421509&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-33792-6_21
DO - 10.1007/978-3-030-33792-6_21
M3 - Conference contribution
AN - SCOPUS:85076421509
SN - 9783030337919
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 338
EP - 353
BT - PRIMA 2019
A2 - Baldoni, Matteo
A2 - Dastani, Mehdi
A2 - Liao, Beishui
A2 - Sakurai, Yuko
A2 - Zalila Wenkstern, Rym
PB - Springer
T2 - 22nd International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2019
Y2 - 28 October 2019 through 31 October 2019
ER -