Improved WPM encoding for coalition structure generation under MC-nets
Improved WPM encoding for coalition structure generation under MC-nets
复制标题
改进了 MC-nets 下联盟结构生成的 WPM 编码
DOI：
10.1007/s10601-018-9295-4
复制
发表时间：
2018-09
期刊：
影响因子：
1.6
通讯作者：
Yokoo Makoto
中科院分区：
文献类型：
--
作者：
Liao Xiaojuan;Koshimura Miyuki;Nomoto Kazuki;Ueda Suguru;Sakurai Yuko;Yokoo Makoto
联盟结构生成（CSG）问题在联盟游戏的领域中起着重要作用。它的目标是建立代理联盟，以最大程度地提高全球福利。迄今为止，加权部分MaxSat（WPM）编码已显示高E
The Coalition Structure Generation (CSG) problem plays an important role in the domain of coalition games. Its goal is to create coalitions of agents so that the global welfare is maximized. To date, Weighted Partial MaxSAT (WPM) encoding has shown high efficiency in solving the CSG problem, which encodes a set of constraints into Boolean propositional logic and employs an off-the-shelf WPM solver to find out the optimal solution. However, in existing WPM encodings, a number of redundant encodings are asserted. This results in additional calculations and correspondingly incurs performance penalty. Against this background, this paper presents an Improved Rule Relation-based WPM (I-RWPM) encoding for the CSG problem, which is expressed by a set of weighted rules in a concise representation scheme calledMarginal Contribution net (MC-net). In order to effectively reduce the constraints imposed on encodings, we first identify a subset of rules in an MC-net, referred as a set offreelance rules. We prove that solving the problem made up of all freelance rules can be achieved with a straightforward means without any extra encodings. Thus the set of rules requiring to be encoded is downsized. Next, we improve the encoding of transitive relations among rules. To be specific, compared with the existing rule relation-based encoding that generates transitive relations universally among all rules, I-RWPM only considers the transitivity among rules with particular relationship. In this way, the number of constraints to be encoded can be further decreased. Experiments suggest that I-RWPM significantly outperforms other WPM encodings for solving the same set of problem instances.
登录
查看更多内容
DOI：
10.1002/cpe.3969
发表时间：
2017-03
期刊：
Concurrency and Computation: Practice and Experience
影响因子：
--
作者：
Francisco Cruz-Mencia;Antonio Espinosa;J. Moure;J. Cerquides;J. Rodríguez-Aguilar;Kim Svensson;S. Ramchurn
通讯作者：
Francisco Cruz-Mencia;Antonio Espinosa;J. Moure;J. Cerquides;J. Rodríguez-Aguilar;Kim Svensson;S. Ramchurn
DOI：
10.1007/978-3-031-01558-8
发表时间：
2011-10
期刊：
--
影响因子：
--
作者：
G. Chalkiadakis;Edith Elkind;M. Wooldridge
通讯作者：
G. Chalkiadakis;Edith Elkind;M. Wooldridge
利用计算智能算法解决联盟技能博弈中的联盟结构生成问题
影响因子：
0.7
作者：
Liu Yang;Zhang Guo-Fu;Su Zhao-Pin;Yue Feng;Jiang Jian-Guo
通讯作者：
Jiang Jian-Guo
DOI：
10.1609/aaai.v26i1.8265
发表时间：
2012-07
期刊：
Proceedings of the AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Talal Rahwan;Tomasz P. Michalak;N. Jennings
通讯作者：
Talal Rahwan;Tomasz P. Michalak;N. Jennings
DOI：
10.1145/1064009.1064030
发表时间：
2005-06
期刊：
--
影响因子：
--
作者：
Samuel Ieong;Y. Shoham
通讯作者：
Samuel Ieong;Y. Shoham