IEICE TRANSACTIONS on Information
MaxSAT Encoding for MC-Net-Based Coalition Structure Generation Problem with Externalities
Summary :
Coalition Structure Generation (CSG) is a main research issue in the domain of coalition games. A majority of existing works assume that the value of a coalition is independent of others in the coalition structure. Recently, there has been interest in a more realistic settings, where the value of a coalition is affected by the formation of other coalitions. This effect is known as externality. The focus of this paper is to make use of Maximum Satisfiability (MaxSAT) to solve the CSG problem where externalities may exist. In order to reduce the exponentially growing number of possible solutions in the CSG problem, we follow the previous works by representing the CSG problem as sets of rules in MC-nets (without externalities) and embedded MC-nets (with externalities). Specifically, enlightened by the previous MC-net-based algorithms exploiting the constraints among rule relations to solve the CSG problem, we encode such constraints into weighted partial MaxSAT (WPM) formulas. Experimental results demonstrate that an off-the-shelf MaxSAT solver achieves significant improvements compared to the previous algorithm for the same set of problem instances.
- Publication
- IEICE TRANSACTIONS on Information Vol.E97-D No.7 pp.1781-1789
- Publication Date
- 2014/07/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E97.D.1781
- Type of Manuscript
- PAPER
- Category
- Information Network
Authors
Xiaojuan LIAO
Kyushu University
Miyuki KOSHIMURA
Kyushu University
Hiroshi FUJITA
Kyushu University
Ryuzo HASEGAWA
Kyushu University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Xiaojuan LIAO, Miyuki KOSHIMURA, Hiroshi FUJITA, Ryuzo HASEGAWA, "MaxSAT Encoding for MC-Net-Based Coalition Structure Generation Problem with Externalities" in IEICE TRANSACTIONS on Information,
vol. E97-D, no. 7, pp. 1781-1789, July 2014, doi: 10.1587/transinf.E97.D.1781.
Abstract: Coalition Structure Generation (CSG) is a main research issue in the domain of coalition games. A majority of existing works assume that the value of a coalition is independent of others in the coalition structure. Recently, there has been interest in a more realistic settings, where the value of a coalition is affected by the formation of other coalitions. This effect is known as externality. The focus of this paper is to make use of Maximum Satisfiability (MaxSAT) to solve the CSG problem where externalities may exist. In order to reduce the exponentially growing number of possible solutions in the CSG problem, we follow the previous works by representing the CSG problem as sets of rules in MC-nets (without externalities) and embedded MC-nets (with externalities). Specifically, enlightened by the previous MC-net-based algorithms exploiting the constraints among rule relations to solve the CSG problem, we encode such constraints into weighted partial MaxSAT (WPM) formulas. Experimental results demonstrate that an off-the-shelf MaxSAT solver achieves significant improvements compared to the previous algorithm for the same set of problem instances.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E97.D.1781/_p
Copy
@ARTICLE{e97-d_7_1781,
author={Xiaojuan LIAO, Miyuki KOSHIMURA, Hiroshi FUJITA, Ryuzo HASEGAWA, },
journal={IEICE TRANSACTIONS on Information},
title={MaxSAT Encoding for MC-Net-Based Coalition Structure Generation Problem with Externalities},
year={2014},
volume={E97-D},
number={7},
pages={1781-1789},
abstract={Coalition Structure Generation (CSG) is a main research issue in the domain of coalition games. A majority of existing works assume that the value of a coalition is independent of others in the coalition structure. Recently, there has been interest in a more realistic settings, where the value of a coalition is affected by the formation of other coalitions. This effect is known as externality. The focus of this paper is to make use of Maximum Satisfiability (MaxSAT) to solve the CSG problem where externalities may exist. In order to reduce the exponentially growing number of possible solutions in the CSG problem, we follow the previous works by representing the CSG problem as sets of rules in MC-nets (without externalities) and embedded MC-nets (with externalities). Specifically, enlightened by the previous MC-net-based algorithms exploiting the constraints among rule relations to solve the CSG problem, we encode such constraints into weighted partial MaxSAT (WPM) formulas. Experimental results demonstrate that an off-the-shelf MaxSAT solver achieves significant improvements compared to the previous algorithm for the same set of problem instances.},
keywords={},
doi={10.1587/transinf.E97.D.1781},
ISSN={1745-1361},
month={July},}
Copy
TY - JOUR
TI - MaxSAT Encoding for MC-Net-Based Coalition Structure Generation Problem with Externalities
T2 - IEICE TRANSACTIONS on Information
SP - 1781
EP - 1789
AU - Xiaojuan LIAO
AU - Miyuki KOSHIMURA
AU - Hiroshi FUJITA
AU - Ryuzo HASEGAWA
PY - 2014
DO - 10.1587/transinf.E97.D.1781
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2014
AB - Coalition Structure Generation (CSG) is a main research issue in the domain of coalition games. A majority of existing works assume that the value of a coalition is independent of others in the coalition structure. Recently, there has been interest in a more realistic settings, where the value of a coalition is affected by the formation of other coalitions. This effect is known as externality. The focus of this paper is to make use of Maximum Satisfiability (MaxSAT) to solve the CSG problem where externalities may exist. In order to reduce the exponentially growing number of possible solutions in the CSG problem, we follow the previous works by representing the CSG problem as sets of rules in MC-nets (without externalities) and embedded MC-nets (with externalities). Specifically, enlightened by the previous MC-net-based algorithms exploiting the constraints among rule relations to solve the CSG problem, we encode such constraints into weighted partial MaxSAT (WPM) formulas. Experimental results demonstrate that an off-the-shelf MaxSAT solver achieves significant improvements compared to the previous algorithm for the same set of problem instances.
ER -
English
