第Ⅱ部 協力ゲームの理論 第16章 破産問題 2008/07/02(水) ゲーム理論合宿 Ｍ１ 浦田淳司
内容 破産問題の定式化 タムルードにおける破産問題 CG法 破れた衣服の原理 ミシュナの破産問題のCG法 ｎ人破産問題のCG法(ムズイ)
破産問題の定式化（タムルードの例） ミシュナの3人破産問題 債権額に応じた比例配分ではない….実は提携形ゲームの仁 タムルード：ユダヤ教の重要な経典、紀元400~500年頃編纂された →そのころからゲーム理論はあった！！？ ミシュナの3人破産問題 律法ミシュナに書かれている配分表－Q.遺産を債権者にどう分配するか 遺産 A（債権額100） B（200） C（300） 100 100／3 200 50 75 300 150 債権額に応じた比例配分ではない….実は提携形ゲームの仁
破産問題の定式化 表記 債権者の集合 N＝｛1,2,3,….,n｝ 遺産 E 債権額の組 d＝（d1,d2,.….dn） 解の性質 ただし 任意の破産問題に対して、 ただひとつの利得ベクトルｘを定めるルールFを、破産問題の解という （∑ｘ＝E、ｘ≧0） 解の性質 （１） 単調性：債権者の受取額xiが遺産Eの非減少関数であること （２） 順序保存性：破産問題の解xが (受取額) (不足額)
破れた衣服の原理（ミシュナ） ステーキ肉が1枚ある Aくん ｢半分欲しい」 Bさん ｢全部欲しい」 1／4 もらえる 3／4 もらえる
破れた衣服の原理（残余均等配分） 自分の要求分以外の残りを、相手の取り分として認めるとする 相手へ 均等割り 破産問題として表記すると それぞれが認める相手の取り分 相手の取り分として認めた額の残り プレイヤー1 プレイヤー2 相手へ 均等割り （相手から認められた額）＋（残りの額の均等割り）
破れた衣服の原理（The Contested Garment principle）:CG原理 破れた衣服の原理（不足額均等配分） 2人の要求は全部で3／2であるが、肉はひとつしかない →不足額（D－E）を二人で均等に負担する プレイヤーiの受取額xi=(自分の請求額)－（不足分の均等割り） →残余均等配分に一致 この配分の原理を 破れた衣服の原理（The Contested Garment principle）:CG原理 と呼ぶ
定式化 このルールをCG法と呼ぶ 債権者i,j、遺産E、要求額di 債権者iが相手jに認める額：最低保証額v(j) 二人の受取額は このルールをCG法と呼ぶ
Eの関数として 破産問題（N,E,d） N＝｛1,2｝、0≦E ≦150、d＝(50,100) ①Eが小さい時(E<d1) Max(E-d,0)=0なので、 どちらのプレイヤーもE／2 xi ③ ↓ d2 x2 ② ↓ ②d1<E<d2の時 債権者2の最低保証額のみが増加 債権者1の受取額は固定 ① ↓ d1 x1 x1=x2 ③Eが大きい時(E>d2) 両プレイヤー均等に増加 d1 d2 E
ミシュナの破産問題のCG法 ミシュナの3人破産問題 N＝｛1,2,3｝ E=100,200,300 d=(100,200,300) まず、｛1｝と｛2，3｝の二人破産問題と考える 遺産 A（100） B（200） C（300） 100 100／3 200 50 75 300 150 d＝(100,200+300)＝(100,500) E＝200のとき、x1＝0＋1／2×(200-100-0)=50 N={2,3} E=150 d=(200,300) 利得ベクトル＝(50,75,75) このままだと、E＝100のとき、(50,25,25)となってしまう →順序保存性が成り立たない E ≧ 450のときは、不足額の順序保存性が崩れる。 順序保存性が崩れるのは、 150≦E ≦450、すなわち E≦150の場合は、Eを3人で均等に分け、 E≧450の場合は、不足額D－Eを3人で分ける と破産問題は解決
おわりに 3人破産問題のCG法をn人に拡張して、 n人破産問題のCG法をアルゴリズムで与えることが出来る シャープレイ値、τ値の場合と一致する解を導くアルゴリズムを作ることが出来る 遺産配分は債権額に比例して配分する方法：比例配分法が用いられるが、 債権全ての貨幣の単位を同じ重さをもつものとして、等しく扱っている。 そこに債権者という人間の顔はみえない。 たいして、CG法、シャープレイ値などは それぞれの債権者の債権額がひとつの単位、一体となっている。 そして、債権額の少ない人から、その要求を満たしていくという考え方には、 人としての債権者の顔が見えている。