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

MC-nets における利得分配：上界保証付き ε-コアを求めるアルゴリズム
平山 勝敏

赤木 純

沖本 天太

本稿では，MC-nets のルール集合で記述された提携形ゲームの利得分配問題に対して，代表的な解概念の一つであるε-コアに属する利得ベクトルを求めるアルゴリズムを 2 つ提案する．１つ目のアルゴリズム eCore1 は，MC-netsルール集合と最大不満の最小値に対する上界保証値を入力とし，要求された ε-コアに属する利得ベクトルとその最大不満の値を返す，いわゆる事前保証付きアルゴリズムである．一方，もう一つのアルゴリズムである eCore2 は，MC-nets ルール集合と任意の提携集合を入力とし，ε-コアに属する利得ベクトルとそれが達成する上界保証値を返す，いわゆる事後保証付きアルゴリズムである．本稿では，それぞれのアルゴリズムの理論的性質を示す．

得 pmax を各エージェントにどのように分配するかを1 準備決める問題である．以降，分配の結果，各エージェン

提携形ゲーム (coalitional game) は，エージェント

ト i は xi の利得を得るものとし，それを利得ベクトの集合 A = {1, . . . , n}，および，エージェントの可ル x = (x1 , . . . , xn ) で表す．利得分配問題に対しては能な部分集合（提携 (coalition)）に対する利得を計

いくつかの解概念が提案されている．そのうち，不満算する特性関数 (characteristic function)v : 2 → ℜという概念に基づくコア (core)，ε-コア (ε-core)，最で構成される．

小コア (least core)，および，仁 (nucleolus)，さらにA

提携形ゲームにおける代表的な問題の 1 つに提携構

は，貢献度という概念に基づくシャプレイ値 (Shapley

造形成問題 (coalition structure generation problem)

value) が良く知られた代表的な解概念である．本稿がある．提携構造 (coalition structure) とは，エーでは最小コアとその近似解に相当する ε-コアを扱う．

ジェント集合 A に対する分割であり，提携構造形成問
題では，最大総利得 pmax を達成する A の分割 CS ∗を求める．この問題は NP 困難な問題に属する．

1. 1 ε-コアと最小コア

提携形ゲームにおけるもう 1 つの問題は利得分配問

あ る 利 得 ベ ク ト ル x = (x1 , . . . , xn ) に 対 し ，∑v(S) >i∈S xi を満たす部分提携 S ⊂ A を阻止

題 (payoﬀ division problem) である．これは，最適提携（blocking coalition）という．阻止提携 S が存∗な提携構造 CS を形成することにより獲得した総利在すれば，S のメンバーは利得ベクトル x に対して不満をもち，最適な提携構造 CS ∗ から離脱して独自

Payoﬀ Division in MC-nets: Algorithms for ε-corewith Upper Bound Guarantee.
This is an unrefereed paper. Copyrights belong tothe Authors.
Katsutoshi Hirayama, Tenda Okimoto, 神戸大学大学
院海事科学研究科, Graduate School of Maritime Sciences, Kobe University.
Jun Akagi, 神戸大学海事科学部（現在，株式会社テクノアソシエ）, Faculty of Maritime Sciences, KobeUniversity.に部分提携 S を作る動機をもつ．コアとは，阻止提携が存在しない利得ベクトルの集合 C であり，形式的には，以下の 2 つの条件式を満たす利得ベクトル x

の集合である．
∑v(S) −xi ≤ 0, ∀S ⊂ A,

∑たされた場合の利得である．ある提携 S について，(1)i∈Sxi = pmax .

(2)i∈A

式（1）の左辺は，部分提携 S の利得ベクトル x に対する不満（excess）を表しており，式（1）は不満のPr ⊆ S かつ Nr ∩ S = ∅ のとき，ルール r は提携 Sに適用可能であるという．S に適用可能なルールの全体集合を RS とするとき，任意の提携 S の利得は∑v(S) = r∈RS vr で与えられる．

MC-nets の利点は，任意の特性関数を表現でき，値が正となるような部分提携が存在しないことを意

また，もう一つの簡略記述法である SCG に比べて，味する．ここで，式（1）を∑v(S) −xi ≤ ε, ∀S ⊂ A,個々の提携の特性関数値の計算，および，利得分配問(3)

題に対するシャプレイ値の計算が高速に行えることにに置き換えることにより，コアを一般化した ε-コアある [4]．一方，欠点は，利得分配問題に対するコアが得られる．すなわち，ε-コアとは，任意の部分提携関係の計算に弱く，例えば MC-nets を入力としたコにおいて不満の値が ε 以下である利得ベクトルの集ア非空性判定問題は coNP 完全であることが示され

合 C ε である．ている [2] [6]．

i∈S′

一般に ε′ < ε のとき，C ε ⊂ C ε が成立する．すな

MC-nets におけるコアのアルゴリズムに関する研

わち，ε の値を小さくしていくと，ε-コアは次第に小究は非常に少ない．MC-nets を最初に提案した論文

さくなり，やがて空となる．最小コアとは，すべてのである [4] では，コアのメンバーシップおよび非空性

非空な ε-コアの共通部分 Cε∗であり，以下の線形計画問題の最適解の集合である．
min.

εs.t.

v(S) −∑∑を判定するアルゴリズムのアイデアのみが示されている．一方，我々は，MC-nets を入力とし，制約生成法（列生成法）を用いてコア非空性判定問題を解く

xi ≤ ε, ∀S ⊂ A,i∈S(4)

アルゴリズム [5]，および，最小コアに属する利得ベクトルを求めるアルゴリズム [3] を提案し，それぞれ

xi = pmax .

i∈Aすなわち，最小コアとは，可能なすべての部分提携に実装および評価を行った．

おける不満の最大値（最大不満）を最小化する利得

文献 [3] のアルゴリズムの背景となった理論的成果ベクトルの集合である．また，(4) の線形計画問題のは，線形計画問題 (4) に対して，利得ベクトル x と ε∗最適値を ε∗ とすれば，ε∗ -コア (C ε ) が最小コアとの任意の値の実行可能性を MC-nets のルールの情報なる．

のみを用いて判定する仕組みを考案した点である．

1. 2 MC-nets と価格問題

利 得 ベ ク ト ル の 値 x̂ = (x̂1 , . . . , x̂n )（ た だ し ，∑ni=1 x̂i = pmax とする）と ε の値 ε̂ が，(4) の実提携形ゲームでは，従来，特性関数はいわゆるブ行可能解か否かを判定する際，素朴な方法では 2n − 1

ラックボックス関数とされ，エージェント間の可能な個の制約式を全てチェックする必要があるが，考案し提携を与えれば値を返すものとされていた．近年，特た方法では，以下の整数計画問題（価格問題）の最適性関数の簡略記述法として SCG [1] や MC-nets [4]

値 z ∗ を求め，z ∗ ≤ ε̂ ならば実行可能と判定する．

等が提案されている．

MC-nets では，提携が満たすべきルールの集合 Rによって特性関数を表現する．各ルール r ∈ R は，(Pr , Nr ) → vr という形式で記述され，Pr は存在しなければならないエージェントの集合，Nr は存在して

max.

∑vr βr −∑∑i∈Pr∑i∈A∑である．また，vr ∈ ℜ は，ルール r の条件部が満i∈A∑i∈Nr(1 − αi ) +i∈Prはならないエージェントの集合であり，Pr ∩ Nr = ∅x̂i αii∈A∑αi +(1 − αi ) ≥ |Pr ∪ Nr |βr , ∀r ∈ R+ ,r∈Rs.t.

∑αi ≥ 1 − βr , ∀r ∈ R− ,i∈Nrαi ≤ n − 1,αi ≥ 1,αi , βr ∈ {0, 1}, ∀i ∈ A, ∀r ∈ R.

(5)

ここで，価格問題 (5) における各変数の意味は次の通りである．

• A：エージェントの集合（|A| = n）
• R：MC-nets ルールの集合• R+ ：利得が正である MC-nets ルールの集合

Step 4. z ∗ ≤ ε̂ であれば，x̂ が主実行可能性を満たすため，x∗ ← x̂ および ε∗ ← ε̂ とし，それぞれを出力して終了する．そうでなければ提携
S ∗ = {i | α∗i = 1, ∀i ∈ A} を構成し，提携集合
T に提携 S ∗ を追加する．Step 2 に戻る．

• R− ：利得が負である MC-nets ルールの集合
2. 2 近似アルゴリズム eCore1• Pr ：MC-nets ルール r の条件部で指定された存本研究では，新しい近似アルゴリズムを得るため在しなければならないエージェントの集合• Nr：MC-nets ルール r の条件部で指定された存に，文献 [3] のアルゴリズムの終了条件を一般化する．
まず，以下の補題 1 および 2 を証明なしで与える．

在してはならないエージェントの集合• αi ：エージェント i (∈ A) に対応した 0-1 決定

補題 1 制限されたマスター問題 (6) の最適値 ε̂ は，最小コアを求める線形計画問題 (4) の最適値（最大不変数• βr ：MC-nets ルール r (∈ R) に対応した 0-1 決
定変数満の最小値）ε∗ の下界を与える．
補題 2 価格問題 (5) の最適値 z ∗ は，最小コアを求める線形計画問題 (4) の最適値（最大不満の最小値）

ε∗ の上界を与える．

2 提案アルゴリズム

以上の 2 つの補題を利用して次のような近似アル2. 1 最小コアを求める既存アルゴリズム
制約生成法では，制約の数が潜在的に膨大となる大規模な線形計画問題に対し，一部の制約からなる問題

ゴリズム eCore1 が構成できる．

Algorithm eCore1(R, bound)（制限されたマスター問題）からスタートし，必要なInput: MC-nets のルール集合 R，上界保証値
bound (≥ 0)
Output: ε-コアに属する利得ベクトル x，最大不満の値 ε（ただし ε − ε∗ ≤ bound）

制約を順次追加しながら暫定的な解を繰り返し求め，求めた暫定解がある条件（主実行可能性）を満たすときそれを最適解として返す．なお，主実行可能性の判

Step 1. 提携集合 T の初期値をすべての可能な単独提携の集合とする．
Step 2. 制限されたマスター問題 (6) の最適解(x̂, ε̂) = (x̂1 , . . . , x̂n , ε̂) を求める．
Step 3. (x̂1 , . . . , x̂n ) を用いて価格問題 (5) を解 き ，そ の 最 適 値 z ∗ と 最 適 解 の 一 部 で あ るα∗ = (α∗1 , . . . , α∗n ) を求める．
Step 4. z ∗ − ε̂ ≤ bound が成立すれば，x ← x̂ および ε ← z ∗ とし，それぞれを出力して終了する．
そうでなければ提携 S ∗ = {i | α∗i = 1, ∀i ∈ A}を構成し，提携集合 T に提携 S ∗ を追加する．
Step 2 に戻る．

定，および，それが成立しない場合に追加する制約の決定において，前述の価格問題が重要な役割を果たす．
文献 [3] では，次のようなアルゴリズム LeastCoreを提案した．

Algorithm LeastCore(R)Input: MC-nets のルール集合 R
Output: 最小コアに属する利得ベクトル x∗ ，最大不満の最小値 ε∗
Step 1. 提携集合 T の初期値をすべての可能な単独提携の集合とする．
Step 2. 次の線形計画問題（制限されたマスター問題）の最適解 (x̂, ε̂) = (x̂1 , . . . , x̂n , ε̂) を求める．
min. ε∑s.t.
v(S) − i∈S xi ≤ ε, ∀S ∈ T , (6)∑i∈A xi = pmax ,Step 3. (x̂1 , . . . , x̂n ) を用いて価格問題 (5) を解 き ，そ の 最 適 値 z ∗ と 最 適 解 の 一 部 で あ るα∗ = (α∗1 , . . . , α∗n ) を求める．

このアルゴリズムについて，以下が成立する．
定理 1 (正当性) アルゴリズム eCore1 は z ∗ -コアに属する利得ベクトルを返す．その最大不満の値 z ∗ とその最小値 ε∗ との差は bound 以下である．
証明： 補題 1 と 2 が成り立つことと，同アルゴリズ
ムの Step 4 の終了条件から自明に導ける．

2定理 2 (停止生) アルゴリズム eCore1 は有限時間内する．

で停止する．
証明： 可能な提携の数は高々2 − 1 個であるため，nAlgorithm eCore2(R, T )∗Step 2 から 4 の繰り返しの過程において，提携 S として毎回異なる提携が選択されて提携集合 T に追加

Input: MC-nets のルール集合 R，提携集合 T
Output: 利得ベクトル x，最大不満の値 ε とその最小値 ε∗ との差の上界 bound

されるならば，制限されたマスター問題 (6) はいずれ最小コアを求める線形計画問題 (4) に一致し，そのStep 1. 制限されたマスター問題 (6) の最適解(x̂, ε̂) = (x̂1 , . . . , x̂n , ε̂) を求める．
Step 2. (x̂1 , . . . , x̂n ) を用いて価格問題 (5) を構成し，各決定変数 αi (∀i ∈ A) と βr (∀r ∈ R)の取り得る値を 0 以上 1 以下の実数値に緩和した線形緩和問題

際，z ∗ = ε̂ となるため停止する．従って，Step 4 において，すでに T の要素である提携が S ∗ として選択されることはないという事実（S ∗ ∈/ T ）を示せば充分である．S ∗ は利得ベクトル x̂ に対して最大の不満∑をもつ提携であり，その不満の値 v(S ∗ ) − i∈S ∗ x̂i∗max.

∗が価格問題 (5) の最適値 z と一致する．今，S が構s.t.

成されたため，z ∗ − ε̂ > bound，すなわち，∑v(S ∗ ) −x̂i > ε̂ + bound∑r∈R∑∑x̂i αii∈A∑αi +(1 − αi ) ≥ |Pr ∪ Nr |βr , ∀r ∈ R+ ,i∈P∑r∑i∈Nr(1 − αi ) +i∈P∑rαi ≥ 1 − βr , ∀r ∈ R− ,i∈Nrαi ≤ n − 1,i∈S ∗が成立している．一方，S ∗ ∈ T だと仮定すると，x̂i∈A∑と ε̂ に対して制限されたマスター問題 (6) の制約条件

i∈Aαi ≥ 1,0 ≤ αi ≤ 1, ∀i ∈ A,0 ≤ βr ≤ 1, ∀r ∈ R.

を当然満たすため，∑v(S ∗ ) −x̂i ≤ ε̂(7)を作って，その最適値 l∗ を求める．
Step 3. x ← x̂ および bound ← l∗ − ε̂ とし，それぞれを出力して終了する．

i∈S ∗が成立するはずである．よって矛盾が発生し，S ∗ ∈/Tと結論できる．

vr βr −2

なお，アルゴリズム eCore1 において bound の値を 0 に設定すれば，最小コアを求めるアルゴリズム

LeastCore と同一になる．すなわち，eCore1 は，従来アルゴリズムである LeastCore を特殊ケースとして含む．

2. 3 近似アルゴリズム eCore2
アルゴリズム eCore1 は，制限されたマスター問題(6) と価格問題 (5) を繰り返し解くことにより，最大不満の値 ε がその最小値 ε∗ から bound 以内であることが保証された ε-コア（に属する利得ベクトル）を求める．一方で，価格問題 (5) は整数計画モデルで記述された組合せ最適化問題であり，特にエージェント定理 3 アルゴリズム eCore2 が返す利得ベクトルについて，その最大不満の値 ε と最小値 ε∗ の差は l∗ − ε̂以下である．
証 明： 問 題 (7) は 価 格 問 題 (5) の 線 形 緩 和 ゆ えl∗ ≥ z ∗ (= ε)，補題 2 より z ∗ ≥ ε∗ ，補題 1 よりε∗ ≥ ε̂，よって ε − ε∗ ≤ l∗ − ε̂ が言える．

2

このアルゴリズムの特徴は，利得ベクトル x̂ とともに，x̂ に対する最大不満の値とその最小値 ε∗ との差の上界を付帯情報として返す点である．また，Step2 において，価格問題 (5) そのものでなく，その線形緩和問題を解く点も特筆すべきである．これにより，

eCore2 は線形計画問題を 2 回解いて終了するため，計算速度の大幅な向上が期待できる．

数 n が大きくなると，これを解くための１回あたりの計算コストが増大するとともに，繰り返しの回数も増大すると考えられる．
そこで，任意の提携集合 T に対する制限されたマスター問題 (6) を 1 回だけ解いて得た利得ベクトル x̂を返す単純な近似アルゴリズム eCore2 を新たに導入

3 おわりに本稿では，MC-nets のルール集合で記述された提携形ゲームの利得分配問題に対して，代表的な解概念の一つである ε-コアに属する利得ベクトルを求めるアルゴリズムを提案した．今後の課題は，両アルゴリズムの実際の性能を評価する実験を行うことである．

参 考 文 献[1] Conitzer, V., Sandholm, T.: Complexity of constructing solutions in the core based on synergies among coalitions. Artificial Intelligence, 170,
pp.607–619, 2006.
[2] Greco, G., Malizia, E., Palopoli, L., Scarcello,F.: On the complexity of core, kernel, and bargaining set. Artificial Intelligence, 175(12–13), pp.1877–1910, 2011.
[3] Hirayama, K., Hanada, K., Ueda, S., Yokoo, M.,
Iwasaki, A.: Computing a payoﬀ division in theleast core for MC-nets coalitional games PRIMA2014, pp.319–332, 2014.
[4] Ieong, S., Shoham, Y.: Marginal contribution
nets: A compact representation scheme for coalitional games. Proc. of the 6th ACM conference
on Electronic Commerce (EC-2005). pp. 193–202,2005.
[5] 神谷 竜平，花田 研太，平山 勝敏: 列生成法を用いた提携形ゲームのコア非空性判定アルゴリズム，2013 年
度人工知能学会全国大会（第 27 回） (JSAI-2013) 講演論文集，2013.
[6] Malizia, E., Palopoli, L., Scarcello, F.: Infeasibility certificates and the complexity of the core incoalitional games. IJCAI-2007. pp.1402–1407, 2007.