日本ソフトウェア科学会第 34 回大会 (2017 年度) 講演論文集

MC-nets を用いた提携構造形成問題の MaxSAT 符号化の改良
越村 三幸

廖 暁鵑

野本 一貴

上田 俊

櫻井 祐子

横尾 真

提携構造形成問題は協調ゲーム理論の問題の一つで、エージェント集合を社会的効用が最大となるよう分割する問題である．MC-nets は、問題を簡潔に表現する手法の一つであり、ルールの集合で問題を表現する．我々は以前、MC-nets で表現された問題の MaxSAT 符号化による解法を示した．符号化された問題は、MaxSAT ソルバーによって解かれる．この符号化では、MC-nets のルール間関係の推移律を表す制約数がルール数が増加するにつれて膨大になる問題があった．本発表では、この制約数の削減手法を提案する．また、本手法でどの程度、削減されるのか見積もりを示す．

Coalition Structure Generation (CSG), a main research issue in the domain of coalition games, involvespartitioning agents into exhaustive and disjoint coalitions so that the social welfare is optimized. MC-net
is one of the compact representation schemes for representing CSG. An MC-net consists of a set of rules.
We developed a method which encodes CSG with MC-net into Boolean logic and utilize an oﬀ-the-shelf
MaxSAT solver as an optimization tool for solving the CSG problem. The method has a problem that thenumber of constraints, which represents a transitive relation over rules, becomes enormous as rules increases.
This paper proposes a new method to decrease the number of constraints. We also show an estimate of its
reduction rate.

それ自身によって決まる場合に用いられ、分割関数は1 はじめに他の提携の影響を受ける場合に用いられる．特性関数

提携構造形成問題（CSG:Coalition Structure Gen-と分割関数の記述量はそれぞれ Θ(2n ) と O(nn )（neration）は協力ゲーム理論の問題の一つで、提携のはエージェント数）であり、いずれも現実の問題を記もたらす効用の総和が最大となるようにエージェント述するのはエージェントが増えるに従い困難になる．の集合を分割する問題である．提携とは分割されたこの記述困難性に対処するために、特性関数や分割個々の集合のことである．従来の研究では、各提携の関数の簡潔記述法の提案がマルチエージェントシス

もたらす効用は特性関数あるいは分割関数と呼ばれるテムの研究者らを中心に行われている．本研究で扱ブラックボックスの関数（オラクル）によって与えらう MC-nets(Marginal Contribution Nets) [1] は、特れていた．特性関数は提携の効用が他の提携によらず性関数の簡潔記述法の一つで、ルールの集合で提携の効用を表現する．Liao らは、MC-nets で表現さ

An Improvement of MaxSAT Encoding for Coalition
Structure Generation Using MC-nets.
This is an unrefereed paper. Copyrights belong tothe Authors.
Miyuki Koshimura, Kazuki Nomoto, Makoto Yokoo,
九州大学, Kyushu University.
Xiaojuan Liao, 中国・西南科技大学, Southwest University of Science and Technology (China).
Suguru Ueda, 佐賀大学, Saga University.
Yuko Sakurai, 産業技術総合研究所, National Instituteof Advanced Industrial Science and Technology.

れた CSG を MaxSAT 符号化して解く方法を二つ提案している [3] [5] [4]．一つは rule-based、もう一つはagent-based と呼ばれものである．本稿では、前者のMaxSAT 符号化の制約数を削減する手法を提案する．
MaxSAT 符号化した問題は、MaxSAT ソルバーによって解かれる．ここで、MaxSAT（Maximum Sat-isfiability）は、SAT（Boolean satisfiability）を最適化問題に拡張したものである [2] [6]．

本稿の構成は以下の通りである．まず、2 節にて提この時、r1 と r3 は提携 {a1 , a2 , a4 } に適用可能で携構造形成問題を、3 節にて MC-nets を紹介する．

あ る が 、r2 と r4 は 適 用 可 能 で な い ．こ う し て 、次に、4. 1 節にて従来の MaxSAT 符号化を説明し、

v({a1 , a2 , a4 }) = 2 + 1 = 3 と な る ．す べ て の4. 2 節にてその改良手法を提案する．最後に 5 節にて

提 携 構 造 を 列 挙 す る と 、最 適 な 提 携 構 造 CS ∗ はまとめと今後の課題を述べる．

{{a1 , a2 , a4 }, {a3 }} であることが分かり、V (CS ∗ ) =V ({{a1 , a2 , a4 }, {a3 }}) = 2 + 1 + 3 = 6 となる．

2 提携構造形成問題

Ohta らは、MC-nets によって特性関数が記述されエージェントの全体集合を A = {a1 , . . . , an } とすている場合に、提携構造形成問題を混合整数計画法

る．エージェントの部分集合 C ⊆ A を提携と呼ぶ．提（mixed integer programming）を利用して解く手法

携は空でない（C ̸= ∅）とする．A を提携に分割するを提案している [7]．この手法はルールの利得はすべことで得られる提携の組み合わせを提携構造と呼ぶ．て正であると仮定しているが、後に、Ueda らによりつまり、提携構造 CS はエージェトの部分集合の集合負の利得にも対処できるように拡張された [10] [8]．

CS = {C1 , . . . , Ck | Ci ⊆ A} で Ci ∩ Cj = ∅ (i ̸= j)∪と Ci ∈CS Ci = A を満たす．て、提携構造形成問題を解いている．4 節で述べる

特性関数 v は、提携 C の効用を与えるもので、CMaxSAT 符号化もこの形式化に基づく．これはルー

これらは、MC-nets のルール間の関係に着目し→ R）．

ル間の関係に着目した符号化なので rule-based と呼提携構造 CS の効用 V (CS) は、CS に含まれる提携∑の効用の総和である（V (CS) = Ci ∈CS v(Ci )）．提ばれる．これに関して、ここでは 4 節の議論に必要携構造形成問題は、最大の効用をもたらす提携構造

定義 2 (実現可能なルール集合) ル ー ル 集 合 R′ (⊆CS ∗ を見つける問題である．

R) について、任意のルール r ∈ R′ が必ずいずれから実数への関数として与えらえる（v : 2A

な定義と定理を述べる．

かの提携に適用可能であるような提携構造 CS が存

3 MC-nets

在するとき、「R′ は実現可能なルール集合である」とIeong と Shoham は、特性関数を簡潔に記述する手いう．

法として、MC-nets を提案した．これは、特性関数

提携構造形成問題は、ルールの利得の総和∑r∈R′ vr′をルールの集合によって簡略に記述する手法である．

を最大化する実現可能なルール集合 R を探索する問

定義 1 (MC-nets) MC-nets は提携が満たすべき題に等しい．

ルールの集合 R によって記述される．任意のルール

定義 3 (ルール間の関係) 任意の 2 つのルール r とr ∈ R は、(Pr , Nr ) → vr という形で表される．Prr′ の間の関係を次の 4 つに分類する．と Nr はそれぞれ「存在しなければならない」及び「存在してはならない」エージェントの集合であり、Pr ⊆ A、Nr ⊆ A、Pr ∩ Nr = ∅ である．vr ∈ R は、r が満たされた場合の利得を表す．提携 C についてPr ⊆ C かつ Nr ∩ C = ∅ が成り立つとき、r は C に同提携で両立可能 Pr ∩ Pr′ ̸= ∅ ∧ Pr ∩ Nr′ =P r ′ ∩ Nr = ∅両立不可能 Pr ∩ Pr′ ̸= ∅∧(Pr ∩ Nr′ ̸=∅ ∨ Pr′ ∩ Nr ̸= ∅)他提携で両立可能 Pr ∩ Pr′ = ∅ ∧ (Pr ∩ Nr′ ̸=∅ ∨ Pr′ ∩ Nr ̸= ∅)適用可能であるという．C に適用可能なルールの全体∑集合を RC とする時、C の効用は v(C) = r∈RC vr

独立 Pr ∩ Pr′ = ∅ ∧ Pr ∩ Nr′ = Pr′ ∩ Nr = ∅で与えられる．

MC-nets のルール集合を、各ルールをノード、ルー

例 1 A = {a1 , a2 , a3 , a4 } として、次の 4 つのルール

ル間の関係をエッジとしたグラフで表現することがでが与えられているものとする．
r1 : ({a1 , a2 }, ∅) → 2 r2 : ({a1 , a2 }, {a4 }) → −2

きる．次の定理は、ルール集合が実現可能であるため

r3 : ({a1 , a4 }, ∅) → 1定理 1 ルール集合 R′ は、以下の条件を同時に満た

r4 : ({a3 }, {a2 }) → 3の必要十分条件を示す．

すとき、かつそのときに限り実現可能である．
′1. R は、「両立不可能」なエッジで連結されたルール対を含まない．

2. R′ に含まれる任意のルール対が「他提携で両立

4. 1 従来手法到達可能性の推移律を表す次のようなハード
節 を ル ー ル の 3 つ 組 (ri , rj , rk ) ご と に 用 意 す る（1 ≤ i < j < k ≤ n）．

可能」なエッジで連結されているとき、このルー

1. ¬S(i, j) ∨ ¬S(j, k) ∨ S(i, k)

ル対は「同提携で両立可能」なエッジによって到2. ¬S(i, j) ∨ ¬S(i, k) ∨ S(j, k)

達不可能である．

3. ¬S(i, k) ∨ ¬S(j, k) ∨ S(i, j)
このような推移律のためのハード節は全部で n C3 ·3 =4 MaxSAT 符号化

n · (n − 1) · (n − 2)/2 個必要となる．

MaxSAT は、SAT の最適化版で、SAT では解に優定義 4 (従来の MaxSAT 符号化) R を MC-nets の劣はないが、MaxSAT ではあり、最適解が MaxSATルール（その効用は正）の集合とする．各ルール解となる．

(ri : (Pi , Ni ) → wi ) ∈ R に対し、ソフト節 (Bi , wi )MaxSAT では、問題はハード節とソフト節の集合を導入する．また、R の各ルール対 (ri , rj ) に対して、として表される．ソフト節には重みがあり、重みは正ルール間の関係に基づいて次のようにハード節を導整数で表される．重みはそのソフト節の重要性の度合入する (i < j)．

いを示しており、ハード節はどのソフト節よりも重要で必ず満たさなければならない制約を表す．

MaxSAT の目的は、変数の値割当の中で、全ての同提携で両立可能 ¬Bi ∨¬Bj ∨S(i, j), ¬S(i, j)∨

Bi , ¬S(i, j) ∨ Bj .
両立不可能 ¬Bi ∨ ¬Bj .

ハード節を満たし、かつ満たされるソフト節の重みの他提携で両立可能 ¬Bi ∨ ¬Bj ∨ ¬S(i, j).

総和が最大となるものを見つけることである．

独立 ハード節は導入しない．

ここで、節（clause）はリテラル（literal）の選言（論理和）、リテラルはブール変数あるいはその否定

4. 2 提案手法である．節中、否定記号を伴ったリテラルを負リテラ従来手法では、推移律を表すハード節の数は O(n3 )ル、そうでないリテラルを正リテラルと呼ぶ．本稿でのオーダーで増加する．他のハード節の数のオーダー

は節 C の重さが w の時、それらの組 (C, w) でソフは O(n2 ) であり、n が増えるに従い、推移律を表すト節を表す．

ハード節の数が全体の節の大半を占めるようになる．

以下、本稿では、ルールの効用は正値であるとして話を進めるが、負値に拡張するのは容易である．

R = {r1 , r2 , . . . , rn } を MC-nets のルール（その効用は正）の集合とする．各ルール ri ごとに一つの例えば、ルール数が 100 なら 485,100 個、200 なら3,940,200 個のハード節が推移律のために必要となる．
ハード節の増加は、MaxSAT ソルバーの求解速度の低下につながる．

ブール変数 Bi を導入する．直感的には、Bi = 1 は本 節 で は 、推 移 律 を 表 す ハ ー ド 節 を 削 減 す る

ri が実現可能なルール集合の要素であることを意味

MaxSAT 符号化を提案する．この手法では、推移する．
定理 1 を利用するために、到達可能性を表すブール変数 S(i, j) をルールの対 (ri , rj ) ごとに用意する（i < j ）．直感的には、S(i, j) = 1 は ri と rj が共に実現可能なルール集合の要素であり、かつ、「同提携で両立可能」なエッジによって到達可能である、ことを意味する．

律を表すハード節で S(i, j) を正リテラルとして持つものを導入するかどうかを、ri と rj の関係に着目して判定する．
説明を簡単にするために、次のように定義される

S({i, j}) を導入する（i ̸= j ）．

S(i, j) i < j のとき
S({i, j}) =S(j, i) j < i のとき定義 5 (新 MaxSAT 符号化) R を MC-nets のルー

可能なルールがないことに注意されたい．

ル（その効用は正）の集合とする．ソフト節について• r1 と r2 （定義 5 の case 2 を適用）：

は、従来手法と同じように導入する．R の各ルール
対 (ri , rj ) に対して、ルール間の関係に着目して次のようにハード節を導入する (i < j)．

1. 同提携で両立可能：¬Bi ∨¬Bj ∨S(i, j), ¬S(i, j)∨
Bi , ¬S(i, j) ∨ Bj .

¬B1 ∨ ¬B2 , ¬S(1, 2).
• r1 と r3 （定義 5 の case 1 を適用）：
¬B1 ∨ ¬B3 ∨ S(1, 3), ¬S(1, 3) ∨ B1 , ¬S(1, 3) ∨B3 .
• r1 と r4 （定義 5 の case 4 を適用）：

2. 両立不可能：¬Bi ∨ ¬Bj , ¬S(i, j).
3. 上記以外で、ri と同提携で両立可能なルールがない場合：¬S(i, j).

¬S(1, 4).
• r2 と r3 （定義 5 の case 2 を適用）：
¬B2 ∨ ¬B3 , ¬S(2, 3).

4. 同様に上記以外で、rj と同提携で両立可能なルールがない場合：¬S(i, j).
5. 上 記 以 外 の 場 合 †1 ：r と 同 提 携 で 両 立 可j

能 な 全 て の ル ー ル rk に 対 し て 、ハ ー ド 節¬S({i, k}) ∨ ¬S({k, j}) ∨ S(i, j) を 導 入 す る ．

• r2 と r4 （定義 5 の case 3 を適用）：
¬S(2, 4).
• r3 と r4 （定義 5 の case 4 を適用）：
¬S(3, 4).
この例では、定義 5 の case 5 は適用されないので、加えて、ri と rj が他提携で両立可能であるとき、推移律を表すハード節は作成されない．

ハード節 ¬Bi ∨ ¬Bj ∨ ¬S(i, j) を導入する．

例 3 A = {a1 , a2 , a3 , a4 } で、MC-nets ルールが次提案手法で推移律を表すハード節が導入されるのは、定義 5 の case 5 の場合のみである．さらに、rjのように 4 個あるとする．
r1 : ({a1 }, {a2 }) → 2 r2 : ({a2 , a3 }, ∅) → 2と同提携で両立可能なルール rk に限定したハード節

r3 : ({a1 , a4 }, ∅) → 1のみ作成するので相当数のハード節の削減が期待でこのとき、ルール間の関係は次のようになる．

きる．

• r1 と r2 ： 他提携で両立可能

例 2 A = {a1 , a2 , a3 , a4 } で、MC-nets ルールが次• r1 と r3 ： 同提携で両立可能のように 4 個あるとする．
r1 : ({a1 , a2 }, ∅) → 2 r2 : ({a1 , a4 }, {a2 }) → 2• r1 と r4 ： 独立r3 : ({a2 , a4 }, ∅) → 1r4 : ({a3 }, {a2 }) → 3r4 : ({a3 }, ∅) → 3• r2 と r3 ： 独立
• r2 と r4 ： 同提携で両立可能

このとき、ルール間の関係は次のようになる．

• r3 と r4 ： 独立

• r1 と r2 ： 両立不可能

4 個のソフト節が導入される：(B1 , 2), (B2 , 2), (B3 , 1), (B4 , 3).

• r1 と r3 ： 同提携で両立可能• r1 と r4 ： 他提携で両立可能• r2 と r3 ： 両立不可能

4 個のルールの 6 通りの対から、次のようにハード節が導入される．

• r1 と r2 （定義 5 の case 5 を適用）：

• r2 と r4 ： 独立

¬S(1, 4) ∨ ¬S(2, 4) ∨ S(1, 2), ¬B1 ∨ ¬B2 ∨• r3 と r4 ： 他提携で両立可能¬S(1, 2).

ルールが 4 個あるので 4 個のソフト節が導入される：(B1 , 2), (B2 , 2), (B3 , 1), (B4 , 3).

4 個のルールの 6 通りの対から、次のようにハード節が導入される．ここで、r2 と r4 には同提携で両立• r1 と r3 （定義 5 の case 1 を適用）：
¬B1 ∨ ¬B3 ∨ S(1, 3), ¬S(1, 3) ∨ B1 , ¬S(1, 3) ∨B3 .
• r1 と r4 （定義 5 の case 5 を適用）：
¬S(1, 2) ∨ ¬S(2, 4) ∨ S(1, 4).

†1 この場合、ri と rj は「他提携で両立可能」か「独立」のいずれかである．また、rj と同提携で両立可能なルールが少なくとも一つはある．

• r2 と r3 （定義 5 の case 5 を適用）：
¬S(1, 2) ∨ ¬S(1, 3) ∨ S(2, 3).

• r2 と r4 （定義 5 の case 1 を適用）：
¬B2 ∨ ¬B4 ∨ S(2, 4), ¬S(2, 4) ∨ B2 , ¬S(2, 4) ∨数は確率的には、少なくとも 1/4 には減らすことができる．

B4 .
• r3 と r4 （定義 5 の case 5 を適用）：
¬S(2, 3) ∨ ¬S(2, 4) ∨ S(3, 4).

5 おわりに
本稿では、MC-net を用いた提携構造形成問題のr1 と r2 の対からは、推移律を表すハード節は 1 個MaxSAT 符号化の節数の削減手法を提案した．削減だけ作成される．これは、r2 と同提携で両立可能なされるのは、MC-nets のルール間の推移律を表す節ルールが r4 の 1 個だけだからである．同様に、r1 とで、確率的には、従来手法の少なくとも 1/4 に削減

r4 、r2 と r3 、r3 と r4 の対から作成される推移律をできることを示した．1/4 になるのは、a = 1/2 かつ表すハード節もそれぞれ 1 個である．こうして、こc + d = 1/2 のときであり、実際にこの値になることの例で作成される推移律を表すハード節は、全部では稀であると考えられるので、現実の問題ではより4 個である．従来手法だと、作成されるハード節は多く削減される、と予想される．我々の予備的実験で12(= (4 · 3 · 2)/2) 個なので、8 個削減されることがは、MC-nets のルール数が 150（効用は負の場合も分かる．

あり）のあるインスタンスでは、節の数が約 400 万

定義 5 によって導入されるハード節の数を見積もるため、次のようにルール間の関係の確率を考える．

から十数万に削減され、MaxSAT ソルバーの計算時間も 10 秒から 1 秒に短縮できた．
今後、従来手法との詳細な定量的な比較を行う予定

a：同提携で両立可能となる確率

b：両立不可能となる確率である．また、混合整数計画法を利用する解法との比c：他提携で両立可能となる確率較も行いたいと考えている．さらに、分割決定木 [9]d：独立となる確率を用いた提携構造形成問題の解法 [11] [12] にも提案手

確率の定義より a + b + c + d = 1 である．
このとき、定義 5 のそれぞれの場合で導入されるハード節の数は次のように見積もることができる．

法を適用していきたい．
謝 辞 本 研 究 は 、JSPS 科 研 費 JP16K00304、JP17K00307 の助成を受けたものです．

1. a · n C2 · 3
2. b · n C2 · 2
3. (1 − a − b) · n C2 · (1 − a)n−2
4. (1 − a − b) · n C2 · (1 − (1 − a)n−2 ) · (1 − a)n−2
3 と 4 は、n が十分大きければ滅多に起こらないと考えられるので、以降これらの場合を無視する．

5. (c + d) · n C2 · (n − 2) · a．これは推移律を表すハード節の数で、他提携で両立可能な場合は、これに加えて、c · n C2 個のハード節が加わる．
従来手法では、推移律を表すハード節は n · (n −1) · (n − 2)/2 個であったから、提案手法による減少率は、(c + d) · n C2 · (n − 2) · a ÷ n · (n − 1) · (n − 2)/2 =n · (n − 1) · (c + d) · a/2 ÷ n · (n − 1)/2 = (c + d) · aとなる．a + (c + d) ≤ 1 なので、(c + d) · a ≤ 1/4．
つまり、提案手法によって、推移律を表すハード節の参 考 文 献[ 1 ] Ieong, S. and Shoham, Y.: Marginal contribution nets: a compact representation scheme forcoalitional games, Proceedings of the 6th ACM Conference on Electronic Commerce (ACM EC), 2005,
pp. 193–202.
[ 2 ] Li, C. M. and Manyà, F.: MaxSAT, Hard andSoft Constraints, Handbook of Satisfiability, Biere,A., Heule, M., van Maaren, H., and Walsh, T.(eds.),
Frontiers in Artificial Intelligence and Applications,Vol. 185, IOS Press, 2009, pp. 613–631.
[ 3 ] Liao, X., Koshimura, M., Fujita, H., andHasegawa, R.: Solving the Coalition Structure Generation Problem with MaxSAT, IEEE 24th International Conference on Tools with Artificial Intelligence, ICTAI 2012, Athens, Greece, November 7-9,2012, IEEE Computer Society, 2012, pp. 910–915.
[ 4 ] Liao, X., Koshimura, M., Fujita, H., andHasegawa, R.: Extending MaxSAT to Solve theCoalition Structure Generation Problem with Externalities Based on Agent Relations, IEICE Trans-actions, Vol. 97-D, No. 7(2014), pp. 1812–1821.
[ 5 ] Liao, X., Koshimura, M., Fujita, H., andHasegawa, R.: MaxSAT Encoding for MC-NetBased Coalition Structure Generation Problemwith Externalities, IEICE Transactions, Vol. 97-D,
No. 7(2014), pp. 1781–1789.
[ 6 ] 越村三幸, 藤田博: SAT 技術の進化と応用 〜パズルからプログラム検証まで〜：6. MaxSAT：SAT の最適化問題への拡張 -MaxSAT ソルバーの活用法-, 情報処理, Vol. 57, No. 8(2016), pp. 730–733.
[ 7 ] Ohta, N., Conitzer, V., Ichimura, R., Sakurai,Y., Iwasaki, A., and Yokoo, M.: Coalition Structure
Generation Utilizing Compact Characteristic Function Representations, Proceedings of the 15th International Conference on Principles and Practice ofConstraint Programming (CP), 2009, pp. 623–638.
[ 8 ] 一村良, 長谷川隆人, 上田俊, 岩崎敦, 横尾真: MCnets を用いた提携構造形成アルゴリズムの拡張 : 負の利得と外部性の導入, 電子情報通信学会論文誌. D, 情報・システム, Vol. 94, No. 11(2011), pp. 1707–1715.
[ 9 ] Skibski, O., Michalak, T., Sakurai, Y.,
Wooldridge, M., and Yokoo, M.: A Graphical Representation for Games in Partition Function Form,
Proceedings of the Twenty-Ninth AAAI Conferenceon Artificial Intelligence, 2015, pp. 1036–1042.
[10] Ueda, S., Hasegawa, T., Hashimoto, N., Ohta,N., Iwasaki, A., and Yokoo, M.: Handling negativevalue rules in MC-net-based coalition structure generation, Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2012, pp. 795–804.
[11] 野本一貴, 大田一徳, 上田俊, 櫻井祐子, 横尾真: 分割
関数ゲームの提携構造形成アルゴリズム, JAWS 2016,9 月 2016.
[12] 越村三幸, 査澳龍, 野本一貴, 櫻井祐子, 横尾真: 分割
関数ゲームを対象とした提携構造形成問題の MaxSAT
符号化, 2017 年度人工知能学会全国大会 論文集, 5 月
2017.