授 業 を補 助 す るプ ロ グ ラ ム(2>
一 協 力 ゲ ー ム ー
社会情報学科 行 方 常 幸
1.
2.
3.
4.
5.
6.補 遺 7.
参 考 文 献
は じめ に
「協 力 ゲ ー ム 」 の 解 の 計 算 方 法
「協 力 ゲ ー ム」 プ ロ グ ラ ム プ ログ ラム の構 成 ツ リ ー の 利 用 に つ い て
お わ り に
1294804555566777
1.は じ め に
私 が 担 当 す る数 理 的 な科 目(例 え ば,ゲ ー ム理 論 を扱 う 「計 画 科 学 」 等)に お い て,そ の 内 容 を 理 解 す る た め に は,多 くの数 値 例 を実 際 に解 く こ とが 必 要 で あ る もの が 多 い 。 しか しな が ら,人 間 の 手 計 算 で 解 け る 問 題 は,小 規 模 な も の に 限 られ る。 ま た,手 計 算 で 解 け る 問 題 で も,自 分 で 求 め た 答 え が 正 解 で あ る か をチ ェ ッ クす る こ と も容 易 で は な い 。
これ に対 処 す る た め に,協 力 ゲ ー ム理 論 で 有 名 な 解 で あ る,シ ャ ー プ レ イ値, τ一値,仁,団 結 値,最 小 二 乗 準 仁 な ど を計 算 す る プ ロ グ ラ ム を作 成 した の で 本 稿 で 紹 介 す る。 中 規 模 程 度 以 下 の 問 題 に対 して,デ ー タ を 入 力 し,該 当 す る ボ タ ンを押 せ ば,こ れ らの解 を計 算 す る プ ロ グ ラム で あ る 。 この プ ロ グ ラ ム を 有 効 に利 用 す る こ と に よ り,計 算 の 手 間 に必 要 以 上 に と らわ れ ず,解 そ の もの の 性 質 に注 意 の焦 点 を集 め る こ とが 可 能 と な る 。
〔51〕
52 商 学 討 究 第52巻 第4号
2.「 協 力 ゲ ー ム 」 の 解 の 計 算 方 法
この 節 で は本 稿 で扱 う解 の定 義 と計 算 方 法 に焦 点 を当 て て,ゲ ー ム理 論 を説 明 す る。 本 稿 で 扱 うの は譲 渡 可 能 効 用 を持 つ 提 携 形 ゲ ー ム で あ る 。 こ の譲 渡 可 能 効 用 を 持 つ 提 携 形 ゲ ー ム と は(プ レ イ ヤ ー と呼 ば れ る)参 加 者 全 員 の 集 合 1V={1,...,n}と 特 性 関 数vの 組(N,v)で あ る 。vは(提 携 と呼 ば れ る)Nの 各 部 分 集 合S(⊂N)に 対 し て,提 携 値 と呼 ば れ る 実 数v(S)を 対 応 させ る 関 数 で あ り,提 携Sの メ ンバ ー が 協 力 して 得 られ る 利 益 の総 和 を表 す 。
譲 渡 可 能 効 用 を持 つ提 携 形 ゲ ー ム の主 な 関 心 ご とは,全 体 提 携 が 形 成 され る 時 に得 られ る 利 益v(Mを,全 体 提 携 以 外 の 提 携 値v(S)(S⊂ 劫 を参 考 に し て,各 プ レイ ヤ ー に公 平 に分 け る に は い か に す べ きか?で あ る 。 こ の 問 題 に 対 す る答 え と し て,従 来 か ら多 くの 解(値 と も呼 ば れ る)が 提 唱 され て い る。
本 稿 で は こ れ らの 中 か ら,シ ャ ー プ レ イ値,τ 一値,仁,団 結 値,最 小 二 乗 準 仁, レー値 を扱 う。 以 下 で はV(N)≧ ΣV({ブ})と 仮 定 し て お く。
ブ ハダ
シ ャ ー プ レイ 値,団 結 値,最 小 二 乗 準 仁,り 一値 は最 小 二 乗 値 と呼 ば れ る グ ル ー プ に属 す る解 で,次 の よ うに 定 義 さ れ て い る。
M。,s(s=1,̲,n‑1)を 各n(=2,̲)に 対 して 少 な く と も1項 が 正 で あ る,非 負 の 重 み とす る。 こ の 重 みmに 対 す る 最小 二 乗 値Lsmは 次 の最 小 化 問題 の 最 適 解 と して定 義 さ れ る:
各 ゲ ー ム(瑚 の に対 し て
mi癬 郷 〔・(8)一剤2
S≠2V
sub.toΣX」=v(ハ リ
ブ∈2V
こ の 最 適 解 は 陽 に求 め る こ とが で き,次 の よ う に な る こ とが 知 られ て い る 。
授 業 を 補 助 す る プ ロ グ ラ ム(2)53
‑・ 一響+竃 ≒薩 蛾 羅 副
(∀i∈N)(1)
(i)シ ャ ー プ レ イ 値,(i)団 結 値,㈹ 最 小 二 乗 準 仁,㈹ り 一値 は 重 みmが 各 々
(i)鞠 一 ∴ 〔1:1r1(n‑2,…,;s‑1,…,n‑1)
(li)M・,・==(、+、)7
.一 、)〔 て=1)"'(n‑2,…,;s‑1,…,n‑1)
1
㈹
M・ ・s=2・ 一 ・(n=2・ … ・;s=1・ ・…n‑・)
㈹M・,・‑i(為 〔1二1)'1(n‑2,…,;s‑1,…,n‑1)
で 与 え ら れ る時 の 最 小 二 乗 値 で あ る こ と が 知 られ て い る 。 こ れ ら4つ の 重 み mは 箋 〔劉 細 を満 足 す る.こ れ ら4つ の解(値)を 計算 す るに は公
式(1)を直 接 計 算 す れ ば よ い 。
τ一値 は 次 の よ う に 計 算 され る 。 ま ず,上 界 ベ ク トルbと ギ ャ ッ プ 関 数8と 譲 歩 ベ ク トル λ を次 の よ う に定 義 す る:
あ:=・v(M‑v(N‑{ブ}) 9(s)・一愚 あ一v(s)(2)
54 商 学 討 究 第52巻 第4号
λゴ:=min{9(S)1ブ ∈S⊂N}
ゲ ー ム(瑚 の が 準 平 衡 ゲ ー ム な ら ば,す な わ ち,
9(S)≧0(∀S⊂N)
黒 λ・≧9⑳
を満 足 す る な らば,τ 一値 は
τ(N,v):=
9(.〈 り
∂一 λ
恩 λブ
∂
黒 λブ〉・〕
隠 λブー・〕
(3)
と定 義 され る。
ゲ ー ム(N,v)が 準 平 衡 ゲ ー ム で な い 場 合 は,ま ず,ダ ミ ー プ レ イ ヤ ー を 求 め る 。 ダ ミ ー プ レ イ ヤ ー と は
v(sU{i})‑v(s)=v({i})(∀s⊂N‑{il)
が 成 り 立 つ プ レ イ ヤ ーiの こ と で あ る 。 ダ ミ ー プ レ イ ヤ ー の 集 合 をDと し M:=1V‑Dと お く 。 ダ ミ ー プ レ イ ヤ ー の τ 一値 τ(v)は 次 の よ う に 定 義 さ れ
る:
η(N,v):ニv({ブ})(ブ ∈D)
Mに 属 す る プ レ イ ヤ ー の τ一値 は,少 し 面 倒 で あ る が,次 の よ う に 定 義 さ れ る 。 ま ず,0≦ ε≦1と し,乗 法 的 ε一税 ゲ ー ム(M,ve)を 次 の よ う に 定 義 す る:
雌 臨)勲})鄭
授 業 を 補 助 す る プ ロ グ ラ ム(2)55
ε=0の 時,(』4"ε)は(M,v)と 一 致 す る が,準 平 衡 ゲ ー ム で は な い 。 ε=1 の 時,(M,vε)は(M,v)と 一 致 し な い が,準 平 衡 ゲ ー ム で あ る 。そ こ で,(1吻 ε) が 準 平 衡 ゲ ー ム と な る 最 小 の ε を ε*と お き,Mに 属 す る プ レ イ ヤ ー の τ 一値 を
ホ へ
丈瓢 の の τ一値 と 定 義 す る,す な わ ち,
ε*=min{εIO≦ ε≦1,(1吻 ε)は 準 平 衡 ゲ ー ム}(4)
の 時,
η(N,・)・=η(M,vs")(ブ ∈M)
こ れ を 実 際 に 計 算 す る に は 以 下 の よ う に す る(詳 し く は 「補 遺 」を 参 照)。 ま ず,
ホ ホ
ε*と そ の 時 の 上 界 ベ ク ト ル ∂,譲 歩 ベ ク トル λ を 求 め る 。
薩:=vε(M)‑ve(M‑{ブ})(ブ ∈M)
ge(s)・ 一黒 励 ε(s)(5)
λ∫・=minl9ε(S)1ブ ∈S⊂M}
と お く と,
*..
ε.=mlnε
sub・t,・{繋:蹴M)
を解 け ば よ い 。
56
9ε(s)ニ
商 学 討 究 第52巻 第4号
9(tO
+ε Σv(VI)+Σv(M‑{ブ})‑IMIΣv({ブ})(s・M)
ゴ∈M ブ∈M ブ∈M
9(s)
+・v(s)+愚 溜 一{ブ})‑ISI愚 ・({ブ})(s⊆‑M)
とな る こ と に注 意 す れ ば,制 約 式 は εの1次 式 で あ る。 こ こ でg(S)は(2)で 与 え られ る もの で あ る。 従 っ て,次 の 線 形 計 画 問 題 を解 くこ とに帰 着 さ れ る:
*.̲・
ε .‑mlnε
一[v(s)ち 愚 ・(M‑{ブ})‑ISI蕊 ・({ブ})1・
+λ ≦9(s)(∀i,s:i∈s⊆M) 一降({ブ})+Σv(M‑{ブ}
ブ∈ルノ)‑IMI器 醐)]・
+ろ ≦9ω(∀i∈M) sub'to
‑Lz
.Mv({ブ})ち 冷(M‑1ブ})一 畷 ・({ブD]・
ち器 λブ≧9ω ε≦1 ε≧0
λゴ≧0(∀i∈M)
変 数 は εと λブ(ブ∈M)で あ り,こ の 線 形 計 画 問 題 を 解 い た 時 の 目的 関 数 の 値
ホ ホ
が(4)の ε*と 一 致 し,(5)か ら上 界 ベ ク トルb:ニ ゲ と 譲 歩 ベ ク トル λ:=λ ε を 求 め こ れ ら を(3)に 代 入 す れ ばMに 属 す る プ レ イ ヤ ー の τ 一値 が 計 算 で き る 。 以 上 に よ り,準 平 衡 ゲ ー ム で は な い ゲ ー ム の τ一値 は 線 形 計 画 問 題 を 解 く こ と に よ
授 業 を補助 す るプ ロ グラム(2)57 っ て 計 算 で きる こ とが 分 か っ た。
仁 は 次 の よ う に計 算 さ れ る。 まず,(xに 対 す る提 携Sの)不 満 θ(S,x):=
v(S)一 Σ.x,を 定 義 す る。 そ し て,最 大 不 満 を 最 小 に す る,次 の 線 形 計 画 問 題
ブ ヨ
を解 く:
ε1:=mlnε
一偉 撫 錨
こ の 線 形 計 画 問 題 を解 い た 時 の制 約 条 件 を満 た すxの 集 合 をX1と す る。 す な わ ち,
為 一鵡
η ≧ 刀({ブ})(∀ ブ∈1v),
ー
= 濁
v(s)一 為 ≦ ε1(∀s⊂N・s≠ ￠・N) }
このX1が1点 か らな る集 合 な ら ば,こ の 要 素 が仁 で あ る 。そ うで な い 場 合, 以 下 の よ う に進 む 。
s≠ φ,N
…レ [ Σ部 η = ε ⑲ 疋 却 ー
ブ⑧
U,に 属 して い る提 携 の不 満 を ε1未満 にす る こ とは 不 可 能 で あ る。 そ こ で,次 の線 形 計 画 問 題 を解 く:
58
sub.to
商 学 討 究 第52巻 第4号
ε2:=mlnε
Σ 錫=o⑳
ブ∈N
η ≧"({ブ})(∀ ブ∈!v) v(s)一 為 一 ε1(∀s∈ の
v(s)一 黒 η ≦ ・(∀Sgu,・s≠ ￠・N)
こ の 問 題 を 解 い た 時 の 制 約 条 件 を満 た すxの 集 合X,が1点 か らな る 時 は そ の 要 素 が仁 で あ る 。 複 数 個 の 点 か らな る 時 は,更 に 以 下 の よ う に進 む 。
…臨 妻灘 副
とお き,次 の線 形 計 画 問題 を解 く:
εk+1:=mlnε
sub.to
、恥 一・⑳
紛 ≧"({ブ})(∀ ブ∈ 亙) v(s)一 匙 一 ε1(∀s∈ の
v(8)一 愚 η 一 ・・(∀s∈ の
v(8)一 黒 吻 ≦ ・(∀seu,∪ …uu・ ・s≠ 姻
こ の 問 題 を解 い た 時 の 制 約 条 件 を満 た すxの 集 合X,.1が1点 か らな る まで 繰 返 す 。 この 要 素 が 仁 で あ る 。
最 小 値 ε為を 求 め た 線 形 計 画 問 題 か ら 砿 を 求 め る に は 次 の よ う に行 う。 最 小 値 εゐを 求 め た線形 計 画 問題 の 不 等 号 制 約 式
授 業 を 補 助 す る プ ロ グ ラ ム(2) v(s)一 黒 吻 ≦ ・(∀seu・ ∪ …uu・ 一・・s≠￠・M
59
の 中 で,
v(s)一 愚 紛 一・k (6)
とな っ た制 約 式 に 対 応 す る提 携8は 砿 の 要 素 と な る可 能 性 が あ る。 そ こ で, SがU,1の 要 素 で あ る か 否 か を チ ェ ック す る た め に,(6)が 成 立 す るS以 外 提 携
に対 応 す る制 約 式 の 右 辺 の 変 数 εを値 εhにお きか え,Sに 対 応 す る 制 約 式 は そ の ま まで も う一 度 εを最 小 に す る。 新 た な最 小 値 が 元 の最 小 値 と一 致 す る 時 の みSはU,1の 要 素 で あ る 。
以 上 の こ とか ら線 形 計 画 問 題 を繰 返 し解 く こ と に よ り仁 を求 め る こ とが で き る。
3.「 協 力 ゲ ー ム 」 プ ロ グ ラ ム
作 成 した 「協 力 ゲ ー ム」 プ ロ グ ラ ム を起 動 した の が 図1で あ る。 この 図 が示 す よ うに グ ラ フ ィ カル な イ ン タ ー フ ェ ー ス を持 つ ア プ リケ ー シ ョ ンで あ る。
「特 性 関 数 の入 力 」 タ ブ に3人 ゲ ー ム の デ ー タが 入 力 で き る よ う に な っ て い る 。 こ の 図 か ら容 易 に想 像 で き る よ う に,必 要 な ら ば プ レイ ヤ ー の総 数 を変 更 し,提 携 値 を入 力 し,「 値 の 計 算 」 タブ で 解 の 計 算 を行 う。 こ の 「協 力 ゲ ー ム」
プ ロ グ ラム が どの よ う に動 作 す る か を 見 て み る 。
第4号 第52巻
究
討
学
商60
ワ 蝋 畿 事 欝1
、 ㌧
㌧ 、 甜 ≧㌧'^ヤ ≧㌧ 航 ㌧冊'≧ ㌧'
理 、囎 轡 ゴ一}
滋 畿̲繍̲細;1̲紘 皇て
、 、
事 二
懸輸 翻 画' 遷
識 臨 魔 一 細 な
… 宅
、 註' 卍タ 垂
…
…
…
……
…
︑︑いや議
'︑・彦㌧
滋誰、、"ウ 、"、 、 、、'
'辮 躰 、ウ
融
麟襲
犠
憲繰 麟撫鍵 、
響舞
轍 蟻曝 鐡1
1:駕
嚢陣識.ξ ︑難脚
燃轟'
…聾《鰻購
… 薯《難 難ち
驚'脚 一
︑欝∵趨
㌔サ"、
欝1
t、w
㌔笹
嫁 加" 脚
羅∫葦撫 覇
簾鱗︑二鉾劉範8︾︽磐ヤウ♪⁝︑::⁝曳⁝ざ叩 ㌔'"︑㌧'"くく㌧㌧'⁝∋ζヒ垂︑㌔︑︑≧''"㌔≧ぎ'"㌔'''"︑㌔㌔'︑"︑︑︑㌧︑︑︑ ⁝
'蹄笠蛭"㌧㌧"㌧㌧︑'︑︑︑
を起動 した とこ ろ
「協 力 ゲ ー ム 」
1図
以 下 参 照)。
2(図
人 ゲ ー ム の種 々 の値 を求 め る
4次 の
魑
・駈
翻
"、、 ,価
・曽ウ ' '檸、
、… ,、、
譜︑纏'
議i釜
蕪覗︑一購善
翻難鮮
餐 鰍 餓騒・
総 款 一 灘 ・
溜 細轟 1《 糠 豊毒礁 臆 驚直叢携 司ノ磯 撫
',㌧ ぐ 費,爵
'翻
寧灘
⁝獣 蜘
人 ゲ ーム に変更 した とこ ろ
4
2図
授 業 を補 助 す る プ ロ グ ラ ム(2)
興 《餐 一為
1噛 器
糟 耀 畿頑購 i鶴 鵡
噸 窃響鱒
・嬉懲睡 覇 齢 鮎 灘 翻
樋飛容憩 禽瓢 蟻 嚢購 鍍鰯
1…i羅 鍛 翻
、i晒 騰 翻 蟻 麟 鵜鷲麟
61
図3.デ ー タ 入 力 後 の ウ ィ ン ドウ
v(C)=10,v(D)=20,v(AC)=10,v(AD)=20,v(BC)ニ15,v(BD)=25,v(CD)
=30 ,v(ABC)=15,v(ABD)=25,v(ACD)=30,v(BCD)=30,v(ABCD)=
30。 そ の 他 のv(S)は0。
ま ず,注 意 す る こ と は プ レ イ ヤ ー がA,B,C,...と な っ て い る 点 で あ る 。 3人 ゲ ー ム な ら ば,プ レ イ ヤ ー はA,B,Cで あ り,4人 ゲ ー ム な ら ば,プ レ イ ヤ ー はA,B,C,Dで あ る 。4人 ゲ ー ム に 変 更 す る た め に,ウ ィ ン ドウ 上 方 中 央 部 の コ ン ボ ボ ッ ク ス の 右 の 下 三 角 を ク リ ッ ク し,「4」 を 選 び,「 変 更 」 ボ タ ン を 押 す 。
ウ ィ ン ド ウ 下 方 の テ キ ス ト ボ ッ ク ス に 提 携 と そ の 提 携 値 を 入 力 し 「追 加 」 ボ タ ン を 押 す 。 例 え ば,v(AC)=10を 入 力 す る に は,提 携 を 入 力 す る テ キ ス トボ ッ ク ス に,「AC」(小 文 字 で も 可,入 力 す る 順 序 は 問 わ な い,「cA」 で も よ い)
62 商 学 討 究 第52巻 第4号
と入 力 し,提 携 値 を 入 力 す る テ キ ス トボ ッ クス に 「10」と入 力 す る(非 ゼ ロの 有 理 数 が 入 力 で き る)。v(S)=0で あ る提 携Sと 提 携 値0は 入 力 しな い 。 す な わ ち,入 力 され て い な い デ ー タは0と み な す 。 上 記 の デ ー タ を入 力 した の が, 図3で あ る 。
「特 性 関 数 の 入 力 」タブ の ユ ー ザ ー イ ン ター フ ェ ー ス につ い て少 し説 明す る 。 提 携 値 が ツ リ ー構 造 で 表 示 され て い る。 この ツ リ ー で は 「+」 を押 せ ば,そ の ノ ー ドが 「展 開」 し,「 一」 を押 せ ば,そ の ノ ー ドが 「縮 む」。 入 力 済 み の 提 携 値 を削 除す る に は,そ の 提 携 値 を ツ リー 上 で 選 択 し,「Delete」 キ ー を押 す(ま た は,マ ウ ス を右 ク リ ッ ク し,ポ ップ ア ップ メ ニ ュ ー か ら 「削 除 」 を 選 ぶ)。
入 力 済 み の す べ て の提 携 値 を一 度 に削 除 す る に は,「編 集 」メ ニ ュ ー か ら「全 デ ー タの 削 除 」 を選 ぶ 。 同 じ提 携 に違 う提 携 値 を 「追 加 」 し よ う とす る と 「提 携 値 を 変 更 し ます か?」 と表 示 さ れ,「 は い 」 と答 え れ ば,変 更 さ れ る。 入 力 済 み の 提 携 値 を 変 更 す る他 の 方 法 は,そ の変 更 した い 提 携 値 を ツ リー 上 で 選 択 し, マ ウス を右 ク リ ック し,ポ ップ ア ッ プ メ ニ ュー か ら 「変 更 」 を選 ぶ 。 「提 携:」
及 び 「提 携 値:」 テ キ ス トフ ィ ー ル ドに 変 更 した い値 が 入 力 さ れ,「 追 加 」 ボ タ ンの 名 前 が 「修 正 」 に変 わ る。提 携 値 を修 正 し,「修 正 」ボ タ ン を押 せ ば よ い。
「表 示 」 メ ニ ュ ー か ら 「分 数 」,「 小 数 」,「帯 分 数 」 の い ず れ か を 選 択 す る こ と に よ り,数 値 の 表 示 を 変 更 で きる 。
次 に,「 値 の 計 算 」 タ ブ に移 る 。 先 ほ ど入 力 した 非 ゼ ロ の 提 携 値 が 出 力 され て い る(図4参 照)。
「シ ャ ー プ レ イ値 」 等 の6つ の ボ タ ンが 「値 の計 算 」 タ ブ に あ り,該 当す る ボ タ ン を押 せ ば そ の値 が 計 算 され る。 こ こで はす べ て の ボ タ ンを左 上 か ら右 下 の順 に押 す 。 得 られ た 値 は
授 業 を 補 助 す る プ ロ グ ラ ム(2) 63
図4.「 値 の 計 算 」 タ ブ
シ ャ ー プ レ イ 値=(0,1+2/3,9+1/6,19+1/6),τ 一値=(0,0,10,20), 仁=(0,0,10,20),団 結 値=(4+13/18,5+5/18,8+7/36,11+29/36),
最 小 二 乗 準 仁=(‑5/8,1+7/8,9+3/8,19+3/8), レ ー値=(4+31/36,5+5/12,8+7/36,11+19/36)
と な る 。
ま た,τ 一値 を 計 算 す る 際 に,準 平 衡 ゲ ー ム で あ る か 否 か を チ ェ ッ ク す る の で, ど ち ら で あ る か が 出 力 さ れ て い る 。 こ の ゲ ー ム は 準 平 衡 ゲ ー ム で は な い こ と が
分 か る(図5参 照)。
醒 商 学 討 究 第52巻 第4号
一
鞭鐘麟駿簸i灘噛麟縛寵馴蕊・嘱 て響璽tぼ}駅
;;も㍉夢 一ム 艶 す。
;糞 み 鍵 韓興 鍵 携纏 話 て1輔蜷=1窪
,畷 鱒 顛無 蔓豊 激織 購 鍵 繍 聯
、;ilζ臨 講 麟 轄 蔑幅 畔1細 ㈱ 嚇 試 畔 緯
・i冤晦 懸=1翫 蝋 農隠P講.静 ζ鵡 鯵 ㌔r魏 き・》覇懸 き'畢翠轟
、ξ4流 建 概 撰》盤 翻 露 ≧
、〜》(膿麟1:魎
鋳 鞭 輔爵 ひぜ 彊 巨
、il甑購lR膓$h,t.B}ガ 重鯉 聯 ミ甑1鱒 邑 躯iこ錦"雲 醍 帥R櫨 報 轟 馨撃 嘩 鞠r勢一調 灘 譲鞘 雫 憲憂鳥 修
箋伽 漣 謡'
く/紬齢 憩 調 剣 憐 畷 ・薇"鱒 曹 鱒 β 麟 獅"謹 懇
皐鴛
ξ臨 麟)雷 恥 鞠 ζ繍 睾 蟻、 臨 麓 》・'=齢,晦{翻=漁
擁 縫 獅
1晦 瞳 鹸 慈 麟1翠 ノ1臨 勧 軽 麟9.'験 騨1経"駒1・ 緯}as騒 轄'騰.晦 匿く麟ePT糧 騒 鱒 鐙 駁
織 離 臨 謙 糊 癒lifUNS細蝋 酬 騨 細l
llii・'"'MR
鯉 鹸t遭 醸 彰ノ錐,国 くB飴 、馨鋸 〜掩v蹴 覇 吻 毎 ノ懸9t#S韓s鎖 斗纏 纈
図5.種 々 の値
、
4.プ ロ グ ラ ム の 構 成
この 節 で は,「 協 力 ゲ ー ム」 プ ロ グ ラム の 構 成 の概 略 を述 べ る。
まず,私 が 意 図 し最 終 的 に作 成 し たUI(ユ ー ザ ー イ ン ター フ ェ ー ス)は 次
授 業 を補 助 す る プ ロ グ ラ ム(2) 65 の 通 りで あ る。
(A)提 携 値 を 表 示 す る た め に,Javaに あ らか じ め 定 義 さ れ て い る ツ リー 構 造 で あ るJTreeク ラス を用 い る。
(B)近 似 計 算 で は な く可 能 な 限 り正 確 な計 算 を させ る た め に,扱 え る 数 値 は 分 数 とす る 。 数 値 の表 示 は,分 数,小 数,帯 分 数 の3つ が 指 定 で き る よ う
にす る。
(C)こ の 分 数 の 入 力 を処 理 す る 際 に,明 らか な 入 力 ミス は 受 け付 け な い 。 す な わ ち,「0」 か ら 「9」 まで の 数 字,小 数 点 「.」,マイ ナ ス 記 号 「一」,分 数 の 「/」以 外 は入 力 と して 受 け付 け な い 。 更 に,「.」 や 「/」は2個 以 上 入 力 で きな い 。 「一」 は 第2文 字 目以 降 と して 受 け付 け な い 。 分 数 と して 解 釈 で き な い入 力 に対 して は そ の 旨 表 示 し,「0」 と解 釈 す る 。
(D)提 携 を入 力 す る時 に,入 力 ミス は 受 け付 け ない 。 例 えば,3人 ゲ ー ム の 時,可 能 な 入 力 は 「A,a,B,b,C,c」 で あ る の で そ れ 以 外 は 受 け付 け ない 。 次 に,こ れ らを どの よ う に実 現 した か につ い て 述 べ る。 表1に 作 成 した 主 な パ ブ リ ッ ク ・ク ラス を ま とめ て あ る 。 各 パ ブ リ ッ ク ・ク ラス 内 で は多 くの プ ラ イ ベ ー ト ・ク ラ ス を利 用 して い る が,そ の 説 明 は 省 略 す る 。
(A)に関 し て は ツ リ ー の利 用 法 に焦 点 を 当 て て,次 節 で少 し詳 し く述 べ る。
(B)の分 数 を扱 う部 分 がFracク ラ ス で あ る。 こ の ク ラ ス で は,分 数 を,既 約 分 数 と し て,そ の 分 子 と分 母 を保 持 し,加 減 乗 除 最 大 最 小 の 計 算 を し,入 力 文 字 列 か ら分 数 を 求 め,出 力 と して表 示 用 の文 字 列 を作 成 す る。 こ こ で 工 夫 した 点 は 分 子 と分 母 を保 持 す るた め にBiglntegerク ラス を使 用 した こ と,Fracク
ラス に保 持 さ れ て い る分 数 を文 字 列 と して 出力 す る際 に分 数 表 示,小 数 表 示, 帯 分 数 表 示 出 来 る よ う に した こ と で あ る 。 分 子 と分 母 を保 持 す る た め にIong
を利 用 す る こ と も考 え られ るが,分 数 の 累 乗 をす れ ば す ぐ に桁 あ ふ れ が 生 じる た め,Biglntegerク ラス を利 用 した 。Biglntegerク ラス はJavaに あ らか じめ 定 義 され て い る 整 数 を扱 う ク ラ ス で,記 憶 すべ き数 値 を 正 確 に保 持 す る た め に
そ の都 度 必 要 な 桁 数 を確 保 す る 。
(c)を実 現 す る の がFracFieldク ラ ス で あ る 。 こ の ク ラ ス はJavaに あ らか じ
66 商 学 討 究 第52巻 第4号 表1.作 成 し た お も な ク ラ ス
ク ラ ス 名 内 容
ApplicationCooperativeGame main関 数 を 含 む
CharacteristicFunction 「特 性 関 数 の 入 力 」 タ ブ の 実 体 で あ るJPane1 ク ラ ス を 派 生 し た も の
CharField 提 携 の 入 力 用 テ キ ス トフ ィ ー ル ド CooperativeGameFrame 「協 力 ゲ ー ム」 の メ イ ン ウ イ ン ドウ
Frac 分数
FracField Fracの 入 力 用 テ キ ス トフ ィ ー ル ド LinearProgramming 線 形 計画 問題 を解 くク ラス
MyAboutDialog バ ー ジ ョ ン情 報 を 表 示 す る ダ イ ア ロ グ ボ ッ ク ス MyComboBox プ レイ ヤ ー の 総 数 を設 定 す る コ ン ボ ボ ッ クス
め 定 義 さ れ て い る1行 の テ キ ス トを 入 力 す る た め のJTextFieldク ラ ス を 派 生 さ せ,(C)で 述 べ た 機 能 を 持 た せ た も の で あ る 。
(D>を 実 現 す る の がCharFieldク ラ ス で あ る 。 こ の ク ラ ス はFracFieldク ラ ス と 同 様 にJTextFieldク ラ ス を 派 生 さ せ,入 力 さ れ た1文 字 を チ ェ ッ ク し,不 適 切 な も の は 受 け 付 け な い よ う に し た も の で あ る 。
表1に あ る 他 の ク ラ ス に つ い て,簡 単 に 説 明 す る 。ApplicationCooper‑
ativeGameク ラ ス に は こ の プ ロ グ ラ ム の 最 初 の 実 行 ポ イ ン トで あ るmain関 数 が 定 義 さ れ て い る 。 こ のmain関 数 が 最 終 的 に 図1の メ イ ン ウ ィ ン ド ウ 「協 力
ゲ ー ム 」 を 表 示 す る 。
CharacteristicFunctionク ラ ス は 図1の メ イ ン ウ ィ ン ド ウ 「協 力 ゲ ー ム 」 の
「特 性 関 数 の 入 力 」 タ ブ の 実 体(JPane1を 派 生 し た ク ラ ス)で あ る 。 こ の ク ラ ス で ゲ ー ム の デ ー タ の 入 力,保 持,各 値 の 計 算 を 行 う 。 上 方 に あ る ゲ ー ム の プ レ イ ヤ ー の 総 数 「変 更 」 ボ タ ン が 押 さ れ る と,変 更 後 の プ レ イ ヤ ー の 総 数 が 現 在 の 値 と 違 う 場 合 に の み ツ リ ー 構 造 を 変 更 す る 。 こ の 時,変 更 前 の デ ー タ で 変 更 後 の デ ー タ と し て 妥 当 な も の だ け 残 す よ う に す る 。 す な わ ち,4人 ゲ ー ム
授 業 を補 助 す る プ ロ グ ラ ム(2)
嘩 翠 臨 羅 羅 騨響騨騨l
l心 瞬 瞬 傘勤[網}:i)
1了離 ＼:1 、
67
膿華嘩 驚更礁 鞭 チ
図6.注 意 と問 合 せ
を3人 ゲ ー ム に 変 更 す る 場 合,v(D)=5,v(AD)==10等 の デ ー タ は 削 除 す る が, v(AC)ニ15,v(ABC)=30等 の デv‑一・タ は 残 す 。 下 方 に あ る 「追 加 」 ボ タ ン が 押 さ れ た 場 合,提 携 と 提 携 値 の デ ー タ が 妥 当 で あ る か チ ェ ッ ク す る 。 提 携 値 が0 で あ る 場 合,提 携 が 空 文 字 列 の 場 合,同 じ デ ー タ を 入 力 し よ う と試 み た 場 合, 提 携 値 の み 違 っ た 値 を 入 力 し た 場 合,図6の よ う な 注 意 が 表 示 さ れ る 。 入 力 さ れ た デ ー タ が 妥 当 な 場 合,ッ リ ー に デ ー タ を 追 加 す る 。 ッ リ ー の 利 用 法 は 次 節 で 述 べ る 。
CooperativeGameFrameク ラ ス は 図1の メ イ ン ウ ィ ン ド ウ 「協 力 ゲ ー ム 」
68商 学 討 究 第52巻 第4号
で あ る。 メ ニ ュ ー と 「特 性 関 数 の 入 力 」 と 「値 の 計 算 」 タ ブ を表 示 す る 。 「値 の 計 算 」 タ ブ に あ る ボ タ ンが 押 さ れ た 場 合,CharacteristicFunctionク ラ ス に 対 応 す る値 を計 算 し結 果 を返 す よ う に指 示 す る。 返 され た 結 果 を 「値 の結 果 」
タブ に あ る テ キ ス トエ リ ア に表 示 す る。
LinearProgrammingク ラス は τ一値 と仁 を計 算 す る 時 に利 用 され る線形 計 画 問 題 を解 く ク ラス で あ る。こ の ク ラス(を 主 に利 用 して い る ア プ リケ ー シ ョ ン) に 関 して は 別 の 機 会 に 紹 介 す る 。
MyAboutDialogク ラ ス は 「ヘ ル プ」 メ ニ ュ ー か ら 「バ ー ジ ョ ン情 報 …」 を 選 ん だ 時 に,表 示 さ れ る図7の ダ イ ア ロ グ ボ ック ス で あ る。
〆 隙 鱒 鋤 鱒 麟 嚢麟繍瀬 購 鱗ご{1
・多・1嬢蟻 轍 鱒 難知慶藝繋麟難
i瞬 趣 磁嫡 醗 諦確 繍 鵜鰭麟 縣 さ参 ,幹幽 醜 繭騨 遡鋼 鍾臨 冬㌶
図7.バ ー ジ ョ ン情 報
5.ツ リ ー の 利 用 に つ い て
こ の 節 で は,「 特 性 関 数 の 入 力 」 タ ブ の 実 体 で あ るCharacteristicFunction ク ラ ス に お け る ツ リ ー の 利 用 に つ い て 説 明 す る 。 便 宜 の た め,図1を 図8と し て 再 掲 す る 。
CharacteristicFunctionク ラ ス の ユ ー ザ ー イ ン タ ー フ ェ ー ス の 中 央 部 に 配 置
授 業 を 補 助 す る プ ロ グ ラ ム(2>69
し て あ る の が ツ リ ーJTreeで あ る 。JTreeはJavaに あ ら か じ め 準 備 さ れ て い る ッ リ ー で あ る 。 こ の ツ リ ー の ル ー ト ノ ー ド に 「〃 人 ゲ ー ム 」 と 表 示 し,ル ー ト ノ ー ド に 〃 個 の 子 ノ ー ド を 追 加 し 「?人 提 携 」 と 表 示 さ せ る 。 入 力 デ ー タ が あ れ ば,対 応 す る 「?入 提 携 」 ノ ー ド の 子 と し て 新 た な ノ ー ド を 追 加 し,
「"(??)=??」 と表 示 す る 。
ま ず,ル ー ト用 の ノ ー ドrootnodeと し てDefaultMutableTreeNodeク ラ ス の オ ブ ジ ェ ク ト を 準 備 し,こ れ を 引 数 と し てJTreeの コ ン ス ト ラ ク タ を 呼 び 出 し て お く。DefaultMutableTreeNodeク ラ ス はJavaに あ ら か じ め 準 備 さ れ て い る ク ラ ス で あ る 。 親 ノ ー ド に 追 加 す る(子)ノ ー ド もDefaultMutableT‑
reeNodeク ラ ス の オ ブ ジ ェ ク ト で あ る 。 こ れ ら の ノ ー ド に は デ ー タ と し て 任 意 の オ ブ ジ ェ ク ト を 保 持 で き る 。 こ れ を 利 用 し て,rootnodeに は 文 字 列 「n 人 ゲ ー ム 」 を,そ の 子 ノ ー ド に は 文 字 列 「?人 提 携 」 を,そ の 子 の 提 携 値 の デ ー
タ を 扱 う ノ ー ド に は そ の デ ー タ(CoalitionWorthク ラ ス の オ ブ ジ ェ ク ト)を 保 持 さ せ る 。 ノ ー ドに 保 持 さ れ て い る デ ー タ と 表 示 内 容 は 分 離 さ れ て お り,ツ
リ ー セ ル レ ン ダ ラ ー と い う も の を 介 し て,保 持 オ ブ ジ ェ ク ト を 適 切 に 表 示 す る 。
瓢 範叢
1シ燃 盤'1綴人羅擁 冨'駄 華購
婁
図8.「 特 性 関 数 の 入 力 」 ダ ブ(再 掲)
70商 学 討 究 第52巻 第4号
文 字 列 オ ブ ジ ェ ク ト の 場 合 は そ の 文 字 列 を 表 示 し,CoalitionWorthオ ブ ジ ェ ク トの 場 合 は,そ の 内 容 か ら 「v(??)=??」 の 文 字 列 を 生 成 し て 表 示 す る 。
6.補 遺
こ の 節 で は第2節 の 「協 力 ゲ ー ム」 の 解 の計 算 方 法 で 残 して お い た 上 界 ベ ク トル,ギ ャ ップ 関 数,譲 歩 ベ ク トル の 関 係 を導 出 す る。
ゲ ー ム(N,v)に お い て ダ ミー プ レ イ ヤ ー の 集 合 をDと し,M:=IV‑Dと お く。 この 時,
v(s)‑v(s∩ 初 ㌻晶 ・({ブ})(∀s⊂M
が 成 立 す る 。
(N,v)に 対 す る 上 界 ベ ク ト ル,ギ ャ ッ プ 関 数,譲 歩 ベ ク トル は 次 の よ う に 定 義 さ れ て い る:
防:=v(M‑v(N‑{ブ})
9(s)・ 一恩 防 一・⑧
λブ:=min{9(S)1ブ ∈S⊂N}
ま た,
一{ll㌦)側 ブ})㍊
で 与 え られ る(!吻 ε)に 対 す る 上 界 ベ ク トル,ギ ャ ッ プ 関 数,譲 歩 ベ ク トル は次 の よ う に定 義 され て い る:
授 業 を 補 助 す る プ ロ グ ラ ム(2)7Z
薩:=vε(M)‑vε(M‑{ブ})(ブ ∈M)
9ε(s):=黒 薩 一"ε(s)
λ∫:=min{9ε(S)1ブ ∈S⊂M}
さ ら に,ゲ ー ム(N,v)に 対 しベ ク トル ゲ とR9関 数gε を 次 の よ う に 定 義 す る:
房・一{袈{ブ})li:甥
9・(s):=Σ ろ・‑T・(s)(∀s⊂ ハリ ブeS
え∫・=min{9i(S)1ブ ∈S⊂N}(∀ ブ∈ 劫
た だ し,
i・・(s)・一{∴
(s)+恐 。({男):鄭
こ の 時,次 の 命 題 が 成 り立 つ 。 命 題:次 の こ とが 成 立 す る:
9ε(N)=,ge(M)
=9(M)+ε Σv({ブ})+Σv(M‑{ブ})‑IMIΣv({ブ})
ブ∈Mj∈M ゴ∈M
9ε(s)=9ε(s∩M)(s⊆N,s≠.M)
=9(s∩M)
+・v(SAM)ち 漏 詔(M‑1ブ})一 【s曜 し蕊 ・({ブ})
72商 学 討 究 第52巻 第4号
9i(s)≧・(∀SEM)tsら購 ゼ8ξ 留
証 明:ま ず,ブ ∈Mの 時,
あ=v(劫 一v(N‑{ブ})
=v(M)+Σv({kl)‑v(M‑{ブ})一 Σv({h}) h∈Dk∈D
=v(M)‑v(M‑{ブ})
薩 二v(M)一(1一 ε)v(M‑{ブ})一 ε Σv({kl) h∈M‑1ブ}
‑b」+・[v(M‑{ブD+v({ブ})一 愚 ・({k})1
9i(N)う § 琴一ilε(N)
う乙 娩 ン({ブ})一 ・⑳
=蕊 砺 一拶(M)
=9ε(M)
う器 防一v(M)
+ε Σv({ブ})+Σv(M‑{ブ})‑IMIΣv({k})
ゴ∈Mk∈M ブ∈M
=9(M)
+ε Σv({ブ})+Σv(M‑{ブ})‑IMIΣv({ブ})
ブ∈Mブ ∈Mブ ∈M
で あ る 。 次 に,S⊆N,S≠Mの 時,
授 業 を補 助 す る プ ロ グ ラ ム(2)
9ε(s)=ブ≧1房 一iε(s) 一
、。忍 房+、。黒 。・({ブ})
一(1‑一・)[v(s∩M)ち 晶 ・({ブ})ト 黒 ・({ブ})
一
、。暴 諺 一vε(s∩M)
=9ε(s∩M)
㍉ 晶 房一v(snM)+E[v(snM)⊃ 晶 ・({ブ})]
こ こ で,ブ ∈S∩Mの 時,
薩=oε(M)‑vε(M‑{ブ})
‑v(M)一 一(1‑一 ・)v(M‑‑l」})一 ・
k。景 、、、・({k})
‑v(M)一 ・(M‑{ブ})+・[・(M‑{ブ})+v({ブ})愚 ・({k})]
一 あ+・[v(M‑{」})+v({ブ})⊃ ン({ブ})]
従 っ て,
9ε(s)=ず(s∩M)
㍉ 。黒 診 一v(s∩M)
+十(s∩M)+晶 溜 一{ブ})‑i3曜1黒 ・({ブ})]
73
74 商 学 討 究 第52巻 第4号
二9(s∩M)
+εv(s∩M)+Σv(M‑{ブ})‑ls∩MlΣv({ブ})
ブ∈s∩Mブ ∈M
と な る 。
9εと9ε の 関 係 と9ε(S)≧0(∀S⊆ 初 で あ る こ と に 注 意 す れ ば,λ に 関 す る 主
張 は 明 らか で あ る 。(証 明 終 わ り)
こ の 命 題 の 系 と し て,次 の こ と が 明 ら か に 成 立 す る 。 系:
ε*:=min{ε19ε(N)≧0,9ε(S)≧0(∀S⊆.M)}
、瀞 ダ≧ず⑳
な ら ば,こ の ε*は(4)を 満 た し,窃(N,v)=η(M,ve)(ブ ∈.M)と な る 。
プ ロ グ ラ ム 「協 力 ゲ ー ム 」 に お い て も,準 平 衡 ゲ ー ム で は な い ゲ ー ム の τ一 値 を求 め る 時 に,線 形 計 画 問 題 を解 く前 に この 系 の適 用 可 能 性 を調 べ,可 能 な
らば 適 用 して い る。
7.お わ り に
本 稿 で は授 業 を補 助 す る プ ロ グ ラ ム 「協 カ ゲ ー ム」 を紹 介 し た 。 譲 渡 可 能 効 用 を持 つ 提 携 形 ゲ ー ム の6つ の解 を計 算 す る プ ロ グ ラ ム で あ る。 今 の とこ ろ,
プ レ イ ヤ ー の 総 数 と して 最 大 で(「A」 か ら 「Z」の)31人 まで 可 能 で あ る 。今 後 の 発 展 と し て,(1)他 の 解(例 え ば,任 意 の 重 みmを 持 っ た 最 小 二 乗 値)も 計 算 で きる よ う にす る こ と,(2)入 力 と して,特 性 関 数 で は な く,他 の 適 切 に定 義 され た 問 題 を扱 え る よ う に し,そ の 問題 か ら特 性 関 数 を求 め る よ う にす る こ
と,等 が 考 え られ る 。
授 業 を 補 助 す る プ ロ グ ラ ム(2)75
参 考 文 献
[1]行 方 常 幸 「授 業 を 補 助 す る プ ロ グ ラ ム(1)一 行 列 の 演 算 一 」 小 樽 商 科 大 学 商 学 討 究 第52巻 第2・3合 併 号,2001。
[2]行 方 常 幸,行 方 洋 子 「は じ め て の ゲ ー ム 理 論 一 ゲ ー ム 理 論 と 人 間 の 繋 が り一 」 エ フ ・コ ピ ン ト富 士 書 院,1995。
[3]TheoS.H.Driessen:CooperativeGames,SolutionsandApplicationKluwer AcademicPublishers,1988.
[4]ミ ッ シ ェ ル ・マ ニ ン グ 著/玉 川 竜 司 訳 「JBuilderで 学 ぶJava」 プ レ ン テ イ ス ホ ー 刀レ,19980
[5]掌 田 津 耶 乃 「JBuilderで は じ め るJavaプ ロ グ ラ ミ ン グ 入 門 」 秀 和 シ ス テ ム, 2001。
[6]MaryCampione,KathyWalrath,AlisonHum1:TheJavaTutorial,ThirdEdi‑
tion‑AShortCourseontheBasics.AddisonWesley,2001.
[7]KathyWalrath,MaryCampione:TheJFCSwingTutorial‑AGuidetoCon‑
structingGUIs.AddisonWesley,2000.
[8]Campione,Walrath,Huml,TutorialTeam:TheJavaTutorialContinued‑
TheRestoftheJDK.AddisonWesley,1998.
