授 業 を補 助 す る プ ロ グ ラム(4)
一 破 産 問 題 一
社会情報学科 行 方 常 幸
1.
2.
3.
4.補 遺
5.
参 考 文 献 は じめ に
「破 産 問 題 」 とそ の 解
「破 産 問 題 」 プ ロ グ ラ ム
お わ り に
91 92 95 104 113 113
1.は じ め に
私 が 担 当す る数 理 的 な 科 目(例 え ば 「意 思 決 定 論 」 等)に お い て は,そ の 内 容 を 理 解 す る た め に,多 くの 数 値 例 を 自分 で 解 くこ とが 必 要 で あ る 。 しか しな が ら,人 間 の手 計 算 で解 け る問 題 は,小 規 模 な も の に 限 られ る。 また,手 計 算 で解 け る問 題 で も,自 分 で 求 め た 答 えが 正 解 で あ る か を チ ェ ックす る こ と も容 易 で は な い 。 正 解 が 不 明 な た め,演 習 を途 中 で あ き らめ た 経 験 を持 つ の は私 だ け で は な い で あ ろ う。 これ に対 処 す る た め に 「破 産 問題 」 の 解 を計 算 す る プ ロ グ ラ ム を作 成 した の で本 稿 で 紹 介 す る。 中規 模 程 度 以 下 の 問 題 の デ ー タ を入 力 し,該 当 す る タ ブ を表 示 させ れ ば,種 々 の解 を計 算 す る プ ロ グ ラ ム で あ る。 解 法 の違 い を視 覚 で 捉 え る こ とが で き る よ う に工 夫 し た。 この プ ロ グ ラム を有 効 に利 用 す る こ と に よ り,計 算 の手 間 に と らわ れ ず,種 々 の 解 の 定 性 的 な 違 い に 注 意 の 焦 点 を集 め る こ とが 可 能 とな る。
〔91〕
2.「 破 産 問 題 」 と そ の 解 こ の節 で は 「破 産 問 題 」 とそ の 解 を説 明 す る。
表1各 プ レイヤ ーの 要求額
プ レ イ ヤ ー 1 2 3 4
要 求 額 100 300 400 500
次 の よ う な 例 を考 え る:あ る 人 が 資 産1,000万 円 を残 し死 亡 した 。 この 人 に は4人(こ の 人 た ち を プ レ イヤ ー と呼 ぶ)に 借 金 が あ りそ の額(要 求 額 と呼 び, 単 位 は万 円 とす る)は 表1の よ う に与 え られ て い る。 資 産 が 要 求 額 の 和 よ り も 少 な い の で,各 プ レイ ヤ ー に資 産 をい か に分 け るべ きか?と い う問 題 が 発 生 す る。 こ れ が破 産 問題 で あ る。
一 般 的 に,プ レイ ヤ ー の集 合 をN:={1,̲,n},ま た,0<E≦ Σ の φ>0
ゴ ガ
(∀ブ∈N)と し,資 産 をE,要 求 額 をd:=(dl,̲,dn)と す る 時,破 産 問 題 を (E;d)で 表 す 。 破 産 問 題 の 解!は 破 産 問 題(E;d)にEの 配 分!(E;d):=
(fi(E;d),̲,fn(E;d))を 対 応 さ せ る 関 数 で あ る 。Eの 配 分 で あ る こ と か らf は Σ 乃(E;d)=・Eま た,問 題 の 内 容 か ら
ブ∈N
OSf」(E;d)≦d」(∀ ブ∈N)(1)
を 満 た す 。
本 稿 で 扱 う解 は,比 例 配 分 法,Head法,Leveling法,仁,シ ャ ー プ レ イ値, τ一値 の6つ1)で あ る。 仁,シ ャー プ レ イ 値,τ 一値 は破 産 問 題 を 部 分 集 合 と し て含 む よ り広 い 譲 渡 可 能 効 用 を持 つ提 携 形 ゲ ー ム の解 で あ る。
比 例 配 分 法(Prop):
Eをdに 比 例 し て 配 分 す る方 法 で あ る。 これ はEを 配 分 す る 際 に,各 プ レ
1)こ れ ら の 解 の 詳 細 はYoung,Moulin,Driessenを 参 照 。
授 業 を補助 す る プロ グラム(4)93
イ ヤ ー の 要 求 額 の どの1円 も同 等 の 貢 献 を して い る と い う考 え に よ っ て い る 。 式 で書 く と
Pr・恥(E;d)・ 強E(∀ ブ∈N)
i∈2>
Head法(Head):
各 プ レ イ ヤ ー を 同 等 に 扱 い,Eを な る べ く プ レ イ ヤ ー に 均 等 に 配 分 す る 方 法 で あ る 。 均 等 に し た い が 条 件(1)を 満 た す 必 要 が あ る の で,次 の よ う に 若 干
の 修 正 が 必 要 で あ る 。
且eaの(E;d):=min{λ,4ノ}(∀ ブ∈N)
た だ し ・ λ は ΣHeadブ(E;d)=Eを 満 た す 。 ブ ヱ
Leveling法(Lev):
Head法 と 双 対 的 に 各 プ レ イ ヤ ー の 不 足 分 の 一Le%(E;d)を な る べ く均 等 に 配 分 す る 方 法 で あ る 。 式 で 書 く と
Levブ(E;d):=dj‑min{λ,の}(∀ ブ∈N)
た だ し,λ は ΣLevブ(E;d)=Eを 満 た す 。
ノ∈ハ「
仁(NUC):
Eが 小 さい 時 は 且ead法 の 考 え 方 で,Eが 大 き い 時 はLeveling法 の 考 え 方 で 配 分 す る。 式 で 書 くと
Nu・」(E;d)・=={藻
}1:二:議::
た だ し,λ は ΣNucブ(E;d)=Eを 満 た す2)。
ブ∈N
2)詳 し く は,補 遺 参 照 。
シ ャ ー プ レ イ値(Sh):
〃人 の プ レイ ヤ ー が 順 番 に到 着 す る 。 先 着 順 に(ま だ残 っ て い る 資 産 が あ れ ば)自 分 の 要 求 額(も し,要 求 額 に満 た な け れ ば残 っ て い る もの 全 額)を 受 取 る 。 π1通 りの 到 着 順 にお け る 受 取 り額 を平 均 した もの が シ ャー プ レ イ値 で あ る 。 式 で 書 く と
s場(E;d)・ 一÷ 恩 〃(E;d)
脚)・‑min侮m・x{・ ・E‑,。、、、¥。,」、φ}}
た だ し,Hは 〃1通 り の 順 列 の 集 合 で,そ の 要 素 π に お い て π(の は プ レ イ ヤ ー ゴが 到 着 し た 順 番 を 表 す 。
τ一値(Tau):
比 例 配 分 に 似 た 配 分 方 法 で あ る・E≦ 吉 潔 の 時:ま ず,各 プ レ イ ヤ ー の 要 求 額 をEで 抑 え る。 す な わ ち,む=min{E,の(∀ ブ∈N)と す る。 新 た な 破 産 問 題(E;d')の 比 例 配 分 を求 め る 。 そ の 比 例 配 分 に よ る 配 分 が 元 の 要 求 額 の 半 分 を超 え る プ レイ ヤ ー か ら,そ の超 過 分 を取 り,元 の 要 求 額 の 半 分 に抑 え る 。 元 の要 求 額 が 最 大 で あ る プ レ イ ヤ ー は 残 りを貰 う3)。式 で 書 く と
T・巧(E;d)・‑min{P・ ・恥(E;4虚}(∀ ブ∈N)
Tauκ(E;d):=E一 ΣTauブ(E;d) ゴ≠κ
た だ し,dK‑m・x{ddl7'EN}で あ る ・E誌 影 の 時:
T・恥(E;d)・ ・d」‑T・ 砺 〔愚4・‑E;d〕(∀ ブ∈N)
3)詳 し くは,補 遺 を参 照 。
授業 を補 助す るプ ログ ラム(4)95
以 上 が,本 稿 で 取 り上 げ る6つ の 配 分 方 法 で あ る。 こ れ らの 中 で,比 例 配 分 法,Head法,Leveling法,仁 の4つ の 配 分 方 法 は優 先 法(prioritymethod)
と して も解 釈 で きる 。 優 先 法 と は,各 プ レ イ ヤ ー 毎 に,自 分 の 要 求 額 と現 在 自 分 に配 分 さ れ て い る額 の み に 依 存 して 決 ま る優 先 度 が 与 え られ て い て,追 加 の 資 産 を そ の 時 の優 先 度 が 一 番 高 い
と こ ろ に 配 分 す る,と い う方 法 で あ る。 各 々 の 優 先 度r(d,x)は 表 2に 与 え られ て い る。dが プ レ イ ヤ ー の 要 求 額 で,κ が 現 在 配 分 さ れ て い る 額 で あ る 。
次 節 で 紹 介 す る プ ロ グ ラ ム で は 比 例 配 分 法,Head法,Leveling 法,仁 の4つ の配 分 方 法 が 優 先 法 で あ る こ と を視 覚 的 に理 解 で き る よ う に,図 的 解 法 を行 っ て い る。
表2優 先 度
配分方法 優 先 度7(d,x)
比例配分法 4一 κ
4
Head法 一 κ Leveling法 4一 劣
仁
〆4
‑・ 鉛 ・0≦ ・<7
《
4
、4一 ・ 鉛 ・万 ≦ ・≦4
3.「 破 産 問 題 」 プ ロ グ ラ ム
こ の節 で は 「破 産 問 題 」 を解 くプ ロ グ ラ ム を紹 介 す る。 前 節 で 導 入 した 例 を 解 くこ と に よ り,プ ロ グ ラ ム の 利 用 法 を説 明 し,プ ロ グ ラ ミ ン グ の 時 に特 に留 意 した 点 を述 べ る 。
こ の プ ロ グ ラ ム の ア プ リ ケ ー シ ョ ン版 を 実 行 した の が 図1で あ る 。 「デ ー タ の 入 力 」 タ ブ と 「解 の 計 算 」 タ ブ が あ る ウ ィ ン ドウが 表 示 され る。 この 「デ ー タ の入 力 」 タ ブ で デ ー タ を入 力 す る 。 見 て 明 らか な よ う に,必 要 な らば プ レ イ ヤ ー の 人 数 を変 え 「変 更 」ボ タ ンを押 す 。次 に,資 産Eと 要 求 額dを 入 力 す る 。
ワ㎡ル響 畿涛…轡 繕集轡 爆翻 鯉
くれなへ
恥i魏曽 鵡 磁
・辱曝 蘇 灘 醐 麟
蹴 芦 ・鞭 緬 ̲線 認
聾 嶺 鏡 麿二
』 o 婁̲̲̲i.一 一一一̲uil̲̲̲」̲̲̲一
oi 1 。}
図1「 破 産問 題」起 動 時 のウ ィン ドウ
前 節 の 数 値 例 の デ ー タ を代 入 す る と図2の よ う に な る。 「解 の 計 算 」 タ ブ を 押 す と解 が 図 で 表 示 さ れ る。 こ の 「解 の 計 算 」 タ ブ は 「比 例 配 分 」 か ら 「τ一値 」
と 「ま とめ」 の 合 計7つ の タ ブ か ら な る 。
授 業 を 補 助 す る プ ロ グ ラ ム(4)
どジロし テ ヒ
弄 イル轡 鯨 韓 編集鱒 へ鍼 囎 鱗 亀' '… 晶癬.滋 ヂー鳳 屑 繭 綱
霧醸蕪 睡 4
灘輝 且
蓬
欝. 鑓 《㌦ 翻
匿 垂 営 4
融
彊 剛 国一一
=一一一 3001 400
、
、 ,,
、
,
̀
図2 デ ー タの入 力
磁譲藏一 駄 ニ
フ憩噸 蘇{瞬織 嬢 へ♪レ撃面 調 薦
貼 南い}繭wuLma 峨
轡鱗1￠礒鮒 辱
「 …
…
隔
脚⑳ 纏 鋼 掌
=
…
♂88 :
肇一鋤 肋 勲 鞭i
謎禽鍼 庵磁 隷講鋤 舶霞 羅禽錆、類け 壽犠鐙 舶 ぴ
̲贈 ・嬢 晦 盈 鯉鯉騨 苫i .
レ̀…
「
…
, '"8'♂8"♂ ♂ '''''"♂
,
:
,
…
' }
レ 馴
i:…
i…き
i…
i…
、
≡ ミ
、
、 '
へ'
垂醐 箪ぜw罫
盤 舳̲蜘 階 響{、
む 鵜
、"
傾 ぴ
癬甑翻 虚撒 翻溜 滋灘 癒翻齢
・幽」..」・畠....
.昌
97
蒔 釦轡入殉 縣#9篶}
凄求騨{導〔1鐸 鍛雛.顯参 贈鰍fむ3E3臨(海q鮫
爆麟 測
轟求蒸、姻 贈 尊RB8
聾塗撰.㈲
N姻399
勘
授 業 を補 助 す る プ ロ グ ラ ム(4) 99
ひ矧 戚)藁 騒⑭ 麟 ⑳ 汽紺 齢 茅一鋤 λ諏 獅 綱
學 騨 ・彗〔隣 郵・ξq
冥麟籟 辮 郵・β㈱
ご"。.
》 御 蝋 満駅轍 媚i騒㊧ へ声け⑳
暫離 轟 鰹額.奪βq仁・窪纐 β
檎
聾野 プ 扁輔
デー蝋 労 恥 睾愚1 轟雲騨 窪舶 灘或獺 飾
細.覆 銚 鰯 嶽 馨雛 欝騰
ト
'、
、
ロ バ いハア
ユビ ド
鞭壁 蜘7∵ 淵
eξ9実QII
ー⁝⁝⁝ー⁝妻⁝
・'
一
挫1㌶鰹 二蝕}蜘q転eveRng{r名 一 ■サw二ぎkイ 値 ゼ▼飽 蕊 豊楡
ノ
》't亀 多̲
葡 嘆}褒 宗鰯 編築確}汽ル寮鰭
㍉㍉㍑〃'︑'︑(κ㌔四3
轟綴 瀞 夢一働 触 勲 計瞬
澤珍押.㌻囎 簿醸蕪'卸尊 ア戴 憩 τ翻 〔斜q
聾纏辮,鞠臼 丁欝 鋼β
凄球鞭 醐摩 轍 」(剣q
♂L、 ㌔
ノ 差蓬≧,く≧
"
'=
'
'}'}郎 ♂く
'
≧≧華≧く}5
購 働副 撞薗湾ぜ¶・{‡
貫 轡,搬̀,
SUblitdiftefialLevel臨ectw‑一 ゴhイ 槌 丁.覇 鉦tces
≧ ・s,̀7二
》 イルΦ 蘇 ⑲ 編篠欝 柑雌電}
'︑㌔︑・寄欝
鵡 鰻
躯 鱒 礪 麟 礁1
産 問 頴 産E=100D 人 の 要 求 額d:
1〔}0,3007400,500 ヒ例 配 分=
1000/13730〔IO/13,4000/13,5000/!3 ead=
leD,30D,3fie,3eD evelln竃=
25,225,325,425
50,B5暉/3,950/3,1250/3 シ ャー ブ レイ 値=
75,S25i3,925/371225/3 τ一値=
70,21〔},310,410
諌櫛1
授 業 を補 助す るプ ログ ラム(4)101
各 解 の タ ブ に は そ の 解 に よ る 配 分 額 の 値 とそ の 図 的 表 現 が 表 示 さ れ,「 ま と め 」 タ ブ に は す べ て の 解 に よ る 配 分 額 が ま と め られ て い る。
「比 例 配 分 」 か ら 「仁 」 ま で の4つ の タ ブで は 下 部 にあ る 「再 描 画 」 ボ タ ン
、 卿 門卜
7才4ルw輔 瞬 繍 疑 へ」け 蝉 B・・9dr入Ptl麟i騨こ1
翼薄'{留 導求鰍 急β摩
'艶1'ゴ
} 蒲 澱 灘 講難 講 灘 灘 羅 翻 灘 購 灘購臨獅.
3?イ」多曾 衷鑑卿 櫨巣卿 く」け瞭 蒲 潔
饗蟷騨・噸 釜譲笹灘
Ptw鰍 海 瞬嫡霞1
爵藤 、{留 蔓求額・鋤 妻粛顕・噸 更求轡醜
㍍ 甜 仁.繍 焦 脚3仁 て$繍 俘、碍 仁,繍 鑑、㈱ 仁1ε珊
,
: :
1 レ
静 ・9く
,臼,.サ 曽暫● 9
,
し辱 辱顧鴨 「 、 …
おヨ と ト
繍 ㈱ ぬe ̲、tW"wr
酢 駒{臼e
一 仁 シヤー伽描.慨 盈辮
ド ズち ト 鰍1。 ・e譜
P,く群 齢{DG始
紘醗 宜 臼ヨ…劔 掩蹴 蕉 シv"プhイ 破'僧itksu一
'ち ・ ・
汐{ル響 翫 響 羅 慰 相け 響 チ哨嬉砿 漁 瞭い計填,
蔑施' 瀬 難
憂総㌍'士碗 罫求領'継 翼求顎4齢 要求額 首oロ
揖 認 仁、鰍3に9繍 焦{鋤
::
il 塞i=
馬
毒
蚕
'
...く
棄赴
,
…撰 1、ゴ iへ
馬
峯
{毫
ミ'
=
四 ▼7…7… 四7層冒w'.
… 隔 甲 國
描画話ビード
鱗1鱒̲編 マ 〜笥 、
o魏10o
叢乾 圭
…
灘 灘藩…灘 鷲糀灘懲 灘 … 鶯葦
㌦ず'.♪ 、,伍"凸 げ ノ 、㌔ 、^ば,ナ ㍉,,,."げ'㌦ ご"ゴ,^げ ♂
途 中の3時 点 の状態
が 利 用 で き る。 前 節 で 述 べ た よ う に,こ れ らの 配 分 方 法 は優 先 法 と も解 釈 で き る の で,そ の 解 釈 法 で 図示 させ る ボ タ ンで あ る 。 す な わ ち,追 加 の 資 産 を そ の 時 点 で(自 分 の要 求 額 と現 在 の 配 分 額 の み で決 定 され る)優 先 度 が 高 い プ レ イ ヤ ー に 配 分 す る,と い う よ う に 図 示 で きる 。 「仁 」 タ ブ で(必 要 な ら ば 「描 画 ス ピ ー ド」 をス ラ イ ダー で調 節 し)「 再 描 画 」 ボ タ ン を押 す と(「 再 描 画 」 ボ タ ンが 利 用 不 可 能,す な わ ち,淡 色 表 示 に な り),水 色 の 部 分 が 下 方 か ら上 方 へ と移 動 し最 終 の 配 分 額 に達 す る 。 こ れ らの 図 に お い て,各 棒 の水 色 の 部 分 の 上 端 の 縦 軸 方 向 の 座 標 が 現 在 の優 先 度(下 に行 くほ ど高 い)に な る よ う に 図 は 描 か れ て い る 。優 先 法 に従 っ て各 棒 の 水 色 の 部 分 の上 端 が(可 能 な 限 り)水 平 に な る よ う に 上 へ 移 動 して い く。
この よ うな 図 を描 く際 の 注 意 点 と時 間 の 経 過 に従 っ て 表 示 を変 化 させ る(一 定 時 間毎 に処 理 を させ る)方 法 に つ い て以 下 に述 べ る 。
図 を 描 く際 の 注 意 点:
「仁 」 等 の タ ブ の背 景 が 白 い 部 分(JPanel)に 図(赤 色 の棒 の 境 界 と水 色 の 棒)を 描 い て い る。 同 じ タ ブ上 に あ る,例 え ば,「 要 求 額:100」 とい う文 字 列 は描 く必 要 が あ る時 に,一 度 描 け ば,(他 の ウ ィ ン ドウ の裏 に な りそ の 後 ま た
図 を 描 く コ ー ド privateJPaneljPanelFigure=newJPane10{
publicvoidpaintComponent(Graphicsg){
super.paintComponent(9);
mypaintComponent(9);
};
privatevoidmypaintComponent(Graphicsg){
/*gに 現 時 点 で の デ ー タ を 利 用 し て(赤 と 水 色 の 部 分 の)棒 を 描 く ・/
授 業 を補 助 す る プ ロ グ ラ ム(4) 103 表 に 現 れ た 時 に)自 動 的 に 再 描 画 さ れ る 。 し か し な が ら,図 は 以 下 に 述 べ る よ
う に し な い と,再 描 画 さ れ な い 。
図 を 描 くJpanelを 作 る 時 に メ ソ ッ ドpaintComponentを 定 義 し,そ の 中 で 実 際 に 描 画 を 行 う メ ソ ッ ド(こ こ で はmypaintComponentと い う 名 前 に し た)
を 呼 び 出 す 。mypaintComponentの 中 で,呼 び 出 さ れ た 時 点 で の 図 を 実 際 に 描 く(「 図 を 描 く コ ー ド」 参 照)。
一 定 時 間 毎 に 処 理 を させ る方 法:
「再 描 画 」ボ タ ンが 押 され た ら,時 間の経過 に従 って水色 の部分が変化 す る。
これ は次 の よ う に 実 現 して い る。 「再 描 画 」 ボ タ ンが押 され た ら,(処 理 中 に再 度 同 じ処 理 を依 頼 され る こ と を想 定 して い な い た め)こ の ボ タ ン を利 用 不 可 能 に し,一 定 時 間毎 に 通 知 す る タ イマ ー を 起 動 させ る(『 「再 描 画 」 ボ タ ンが 押 さ れ た ら』 を参 照)。
「再 描 画 」 ボ タ ン が 押 さ れ た ら
jButtonAnimate.setEnabled(false);
//「 再 描 画 」 ボ タ ン を 利 用 不 可 能 に す る timer=newTimerO;
//タ イ マ ー を 作 り
timer.scheduleAtFixedRate(newMyTimerTaskO,O,100);
//100/1000秒 毎 にMyTimerTaskのrunメ ソ ッ ド を 呼 び 出 す よ う に 設 定
こ の タ イ マ ー の 通 知 に よ り実 行 さ れ るrunメ ソ ッ ドの 中 で,水 色 の 棒 の 長 さ を計 算 し,そ の結 果 を描 画 させ る。 具 体 的 に は,描 画 の繰 返 し中 な らば,そ の 時 点 で の 仁 を計 算 し,結 果 を 実 際 に表 示 させ る た め に,jPane1Figureに 更新, 再 描 画 す る よ う に命 令 す る(こ れ に よ り,上 述 のmypaintComponentが 実 行
され る)。描 画 の繰 返 しが 終 了 し た な らば,タ イ マ ー を キ ャ ンセ ル し,「再 描 画 」 ボ タ ンを 利 用 可 能 に す る(「runメ ソ ッ ド」 を参 照)。
runメ ソ ッ ド
privateclassMyTimerTaskextends TimerTask{
publicvoidrunO
if(/*描 画 の 繰 返 し 中 か*/){
//現 時 点 の 仁 を 計 算 jPanelFgure.revalidate();
jPanelFgure.repaint();
}else{
timer.cance10;
//タ イ マ ー を キ ャ ン セ ル jButtonAnimate.setEnabled(true);
//「 再 描 画 」 ボ タ ン を 利 用 可 能 に す る
4.補 遣
この 補 遺 に お い て破 産 問 題 の 仁 と τ一値 を求 め る 。 破 産 問 題(E;d)か ら破 産 ゲ ー ム(N,VE;d)が 次 の よ うに 定 義 さ れ る 。
VE・d(s)・一{野{E‑d(N‑s)'o}詳 ず8≠ の
ただL・d(S)・ 一 榊 離 ガ8≠ ② で ある鵡 便 宜のた め
f(ブ):=VE、d({ブ})ニmax{O,E‑d(N)+dS}(∀ ブ∈N)
△(ブ):=VE、d(N)‑VE、d(N‑{ブ})=min{E,dd}(∀ ブ∈N)
と お く 。 ま た,{d,・1ブ ∈N}の 最 大 値 を 与 え る ブ をKと お く4)。
授 業 を補 助 す る プ ロ グ ラ ム(4)ヱ05 (i)E‑d(N)+dK≦0の 場 合:
Kの 決 め 方 よ りf(の=0(∀ ブ∈N)と な る 。 (li)E‑d(N)+dK>0の 場 合:
!(K)=E‑d(N)+aκ>oで あ る 。 ま た,Σ4ノ<Eよ り4ノ ≦E(∀ ブ≠K)と な ブ≠κ
り,従 っ て △(ブ属(∀ ブ緬 で あ る 。 さ ら にE≦4(穿)な ら ばd(N)‑
E≧E2d」(∀ ブ≠κ),E≦ 響 ≦4(N)‑E<dKと な る。 従 っ て,細 一
〇(∀ ブ≠K),△(K)=Eで あ る 。
仁 の 導 出:
概 略 を 述 べ る 。 破 産 ゲ ー ム(2V,VE;d)の 仁 は 次 の よ う に 定 義 さ れ る 。 ま ず,
愚 ザEで あ るx=(x・ ・… ・x・)1こ対 し て ・ 不 満 ・(S・x):=VE・d(S)一 瀞 を 議 す る 。{e(S,x)1∀S⊂N}の 要 素 を 大 き い も の か ら 順 に 並 べ た も の を θ(x)と お
く・ ←1∫脇 ≦△(ブ)(∀」EIV)}恥E}の 領域 におい て辞書 式川頁序 ・)の意
味 で θ(κ)を最 小 に す る κが 仁 で あ る。
9・S',・E、d(S)≦m・xC
ESf(ブ)β 瀞 、△(ブ)}が 成 立 す る ・)・従 っ て,
VE、d(S)一 黒 η ≦m・xCZ ・.s(f(ブ)一 笏)・、黒 、暢 一△(ブ))}
VE、d({ブ})一 η=f(の 一η とVE、d(N‑{ブ})一 Σ κ戸 η 一△(ブ)に 注 意 す る と
i∈ ノV‑{ブ}
θ(X)=(max{max{!(ブ)一 吻,紛 一 △(ブ)}1ブ ∈N},̲)
す な わ ち,θ(x)の 最 初 のn個 の 要 素 は{min{Xj‑f(」),△(」)一 簿}け ∈N}の 要
4)最 大 値 を与 え る ブが2個 以 上 あ る 場 合 は,適 当 に1つ を 選 ぶ 。
5)2つ の ベ ク トル θ(x)と θ(y)の 要 素 を左 か ら順 番 に 比 較 し,異 な る 最 初 の 要 素 の 大 小 を θ(κ)と θ(ッ)の 大 小 と す る。
6)例 え ば,Namekataetal.参 照 。
素 を 小 さ い順 に 並 べ 符 号 を変 え た もの で あ る 。 従 っ て,ま ず,こ れ ら を な るべ く大 き くす る・ ・≦ろ ≦ △(ブ)〆(ブ)で あ る λブに 対 して ・η の 方 程 式
min{錫 一∫(ブ),△(ブ)一 η}=λ ブ
を 解 く と,
紛 鯛 鵬 〔≦!(ブ)ち △(ブ))ま た 脚,)一 △(棚 〔≧ ∫(ブ)ち△ω 〕
と な る.こ れ らは λ≧・を 利 用 して の(λ)‑min{f(ブ)+λ ・f(ブ)S△(ブ)}ま
鵬(λ)‑m・x{△(ブ)一 λ・!(ブ)ち△(ブ)}と 書 き直 す こ とが で きる 。{ろ1ブ∈N}
を な る べ く大 き く し,Σ 吻(Z)=Eと す る に は
ノ∈…ハ「
毎(λ)=
min(f(ブ)+λ ・f(ブ)S△(ブ)}
m・x{△(フ)一 λ・!(ブ)3△(ブ)}
Σ(!(の+△(の)
forES2∈N
forE≧
2
Σ(!(の+△(の)
i∈1>
(2)
2
た だ し,λ は Σ η(R)=Eを 満 た す 。 こ の(紛(λ))ブ ∈Nが2節 『「破 産 問 題 」
ブ ノ
と そ の 解 』 のNucで あ る こ と に 示 せ ば,こ れ が θ(x)を 辞 書 的 順 序 の 意 味 で 最 小 に す る κ,す な わ ち,仁 で あ る こ と が 分 か る 。
(i>E}d(1>)+dK≦Oの 場 合:
Nl:={ブ ∈Nld」 ≦E},N2:=N‑Nlと お く と,
響 に辱 沌 鷺 ⊥歪}
!(ブ)=0,△(ブ)=min{E,dj}(∀ ブ∈N)で あ る の で,
Σ(∫(ブ)+△(ブ))
ブ∈2>
2
授 業 を補 助 す る プ ロ グ ラ ム(4)
Σ φ+1ハ 引E
=ゴ ∈八〜
2
と な る 。 従 っ て,N2≠ の の 時,E≦
紛ω=1:llli
瀞 優 〕‑d(Nl2)
従 っ て,min圃 一min{R・ 一(ブ ∈N2)と して も良 い・
碗=② の 時,次 の よ う に書 け る。
毎ω一{1∴}
(li)E‑d(劫+dK>0の 場 合:
Ml:={ブ ∈NIE‑d(N)+の ≦0},M2:=N‑Mlと お く。K∈M2で あ り,
f(フ)一{E‑d(舟)+φ 畿 笠
△(ブ)一{鵡 E}鱗
107
≧EforlN,1≧2
ラ4(N)lsdg1K+E≧Ef・ ・N2‑{K}
‑EIS/!IN)f6r1>2一 の d(N)
2で あ り・
雪}鉛 ・ブ∈珊
・斜 鉛・熾
+IN・IE≧Eで あ る の で,Rは 号 を超 え る こ と は な い.
{害}
雪}f・ ・E≦ag/N)
髪f・ ・E≧ 響)
で あ る.眺 響),(B)E>撃 娠<E,(c)E>
分 け て 考 察 す る 。 d(ハ今(
A)E≦ の 時:2
Σ(∫(ブ)+△(ブ)) M2={K},△(K)=Eで あ る の で,ノ ∈N2
(2)の最 初 の 表 現 を 利 用 し て,
η(λ)=
た だ し,λ ≧
E‑2
す る 。
d(N)‑dκ
d(N)‑dK
η ω==minλ,一
(た だ し,λ=E‑
d(劫(
B)E>2
△(K)=dK,d(M2)≦d(N),‑d(N)≦‑Eで あ る の で,
d(劫
,dK≧Eの 場 合 に2
=Eと な る 。 従 っ て,
min{λ 喜}f・ ・ブ≠K
min(E‑d(A・)+dK+λ2E‑4穿)+4κ}勧 一κ
で あ る 。2
>d(Nl‑4K≧ 薯(∀ ブ≠K)に 注意す れば これは次の解 と一致
圃 d(㌻4κ
一穿 一 〔響)‑E〕 ≦争
,dK<Eの 時:
授 業 を補 助 す るプ ログ ラム(4)
濠(ノ(ブ)+△(ブ)) ‑d(N)+d(M2)+(E‑d(N))IM、1
109
(2)は
2
{鑓鵯
≦E
紛(λ)ニ
2
forM2={K}
forIM,1≧ ≧2
m・x{φ 一樹f・ ・ブ∈Ml
m・X(d」‑R・d」‑4(学}勧 ∈M2
と な る 。 ま ず,次 の 方 程 式 の 解 を 求 め る 。 Σ .y」(z)=E
ゴ ガ
巧(λ)‑m・x{φ 一樹 一の 一min{λ 薯}
d(N)≧E>d(1)・ 恩 の(・)・d(N)・
、訓 糾4(1)で あ り・恩 乃(λ)
は 騨 調減 少関数 であ るので,
、恥 郎)‑Eと なる承 割 が憶 に存
在 す る・L・={ブ ∈嘱 一樗}と お}ナば 肥 であ り,
、Σ(姻+黒 誓 一E
d(N)+d(L)‑2E λ*=
21Li が 成 り立 つ 。 ま た,
ズ<一>E
一d(N)+許 一2Ef・ ・L・={K}
≦4(笠FEf・ ・ILI≧2
2<薯(∀ 熾)
,dK≧Eの 時:
=Eと な る か ら, d(N)‑E
以 上 か ら,L⊃M2で あ り,結 局,x(λ')=.y(λ*)で あ る こ と が 分 か る 。 4㈹(
C)2
△(K)ニEで あ る 。d(N)‑E≧d(N)‑dK≧ φ(∀ ブ≠K)よ りM2={K}と な る 。 Σ(!(ブ)+△(ブ))
」∈ノV 2
(2)の2つ 目 の 表 現 を 利 用 し て
毎(λ)=
た だ し,λ ≧d(N)‑dKで あ る 。d(N)‑2E+璽 ≦璽 とd(N)‑2E
一d(N)‑E+
2
η(λ)=max4ノ ー λ,一
(た だ し,λ=
τ一値 の 導 出:
こ の 破 産 ゲ ー ム はsemiconvexで あ り,semiconvexな ゲ ー ム のtr値 Tau(E;d)=(Tau1(E;d),̲,TaUn(E;d))は
m・x{嗣 争}勧 ≠K
m・x(E‑Z・22!t±‑gCgSI‑d(N)+4K}f・ ・ブーκ
+.4些222222
4K穿 讐(
∀ブ≠K)に 臆 す ると,こ れは次 の解 と一致す る・
{雪}
姻 「ノE+dK)
授 業 を 補 助 す る プ ロ グ ラ ム(4)111
T・砺(E;d)・ 一!(ブ)+Σ 輪 票}))〔E㌦ 暑 ∫(の 〕(∀ブ∈N)(3>
i∈2V
と'な る 。Tau(Σdi‑E;d)=d‑Tau(E;d)カ ミ成 立 す る こ と が 分 か っ て い る の
ゴ∈ 〈τ
Σd∫
で,〇 二≦E≦ ゴ酬 の 範 囲 でTau(E;d)を 求 め れ ば よ い 。 次 の2つ の 場 合 に 分2
け て 考 察 す る 。(i)E‑d(N)+dκ ≦Oの 場 合 と(li)E‑d(N)+dK>0の 場 合 で あ る 。
(1)E‑d(劫+dK≦Oの 場 合:
f(の=0(∀ ブ∈N)で あ る の で,
T・砺(E;d)一 弟 〆E(∀ ブ∈N)
ゴ ノ
た だ し,d7==min{E,φ}(∀ ブ∈N)で あ る 。
次に・T・U」(昨 弟 〆E嚇 を示織 ≧1であることに注意する
i∈2V
Σ41
と ・E≦ 弩 を 示 せ ば+分 で あ る ・N・ ・=u∈ ・ZVId」〈‑E}と お く と
Σ41 Σ 一d,+(n‑IN、1)E '∈S2∈N'
2≧E
で あ る・ 何 故 な ら,N・ 一鵬 は仮 定E≦ag/N)よ り成 立 す る。n‑IN・1≧2
の 時 はdi>Oよ り成 立 す る 。E‑d(N)+dK≦Oよ り Σd」+E≧2Eで あ り,
ブ≠κ
ノV1==N‑{K}の 時 も 成 立 す る 。
従 っ て,T・ 砺 働 一P・・P」(E;d')・min(P・ ・P」(E;6劇 で あ る こ と が
示 さ れ た 。TaUK(E;d)=E‑ZTau」(E;d)は 当 然 成 立 し て い る 。
ブ≠K
(li)E‑d(M+dK>0の 場 合:
!(フ)一し 一d(∴ 血 髭諜
△(ブ)一{髪鑑媛
で あ る 。 こ れ ら を(3)へ 代 入 す る と,
T・uブ(E;d)一 ・+2(話 一㊥(d(N)‑4"一 吉 φ(∀ブ≠K)
d(N)‑dK TauK(E;d)=E‑d(N)+dK+(d(N)‑dK)2(d(N) ‑dK)
d(N)‑dK
=E‑
2
=E‑
.Z.TaU」(E;d) ゴ ズ
また・d7=min{E蝋 露 婚 こ注意すると
PrOPソ(E;d')=
の EE
+d(N)‑dK
E EE
+d(N)‑dK
forブ ≠K
forブ=K
El
E+d(N)‑dK>‑2一 で あ る の で ・
T・砺(E;d)‑min(P・ ・P」(E;4玩音 小 ∀ブ≠K)
TaUK(E;d)=E一 ΣTa馬(E;d)
ブ≠κ
が 成 立 して い る こ とが 分 か る 。
授 業 を 補 助 す る プ ロ グ ラ ム(4) 113
5.お わ り に
本 稿 で は 「破 産 問 題 」 の6つ の 解,比 例 配 分 法,Head法,Leveling法,仁,
シ ャー プ レイ 値,τ 一値 を計 算 す る プ ロ グ ラム を紹 介 した 。 特 徴 は,解 を 図 で 表 示 した 点 で あ る。 こ れ に よ り,こ れ ら6つ の 解 の考 え 芳 の 違 い が 視 覚 を通 じて 理 解 で きる よ う に な り,適 用 す べ き状 況 に 依 存 して,ど の 解 を利 用 す べ きか の 判 断 が 容 易 に な る こ とが 期 待 さ れ る。
[1]
参 考 文 献
Young,HP.:Equity‑InTheoryandPractice,PrincetonUniversityPress, 1995.
[2]Moulin,旺:AxiomsofCooperativeDecisionMaking,CambridgeUniversity Press,1988.
[3]Driessen,T.S.H.:CooperativeGames,SolutionsandApplications,Kluwer AcademicPublishers,1988.
[4]Namekata,T。&T.S.HDriessen:BargainingPropertyofNucleolusandτ ・
ValueinaClassofTU‑Games,Computers&MathematicswithApplications 41,703‑721,(2001).
