協力ゲームと結婚定理

協力ゲームと結婚定理
学生団体 POMB ゲーム理論班
Abstract
このレポートでは、ゲーム理論、特に協力ゲームの「コア」という概念について詳しく
述べている。前半で主な定義を述べ、後半では、男女が結婚相手を考える状態を例として
考察した。この考察を通して、コアとはなにか、コアの概念を用いれば、日常にありがち
な現象をどのように捉えることができるのかを理解していただければ幸いである。
1
はじめに 1.1
研究の動機 ゲーム理論班は、広範なゲーム理論の知識を修得することを目標にして、多く
のゲーム理論的な考え方を浅く広く学んでいった。その中でも、より具体例が多
い「協力ゲーム」に興味を持ち、この研究を開始した。
1.2
ゲーム理論とは、協力ゲームとは そもそもゲーム理論において、ゲームとは、複数人（プレイヤーと呼ぶ）が何
らかの行動（戦略と呼ぶ）をして、その結果何かが起こるが、何が起こってほし
いかはそれぞれの人によって違っている状態のことを指す。例えば、将棋などは
ゲーム理論的な意味でゲームである。各プレイヤーがコマを動かし、その結果何
が起こるかは分からないが、お互いはそれぞれ「自分が勝ちたい」と考えている
からだ。この、ゲーム理論的ゲームを考察する学問がゲーム理論である。
ゲーム理論は、大きく分けて、非協力ゲームと協力ゲームに分ける事ができる。
非協力ゲームとは、参加するプレイヤー同士が協力することができないゲームで
ある。先ほど例に上げた将棋や、ジャンケンなどが、非協力ゲームの代表的な例
である。一方、協力ゲームとは、参加するプレイヤー同士が話し合い、提携でき
るゲームである。多数決などをその例としてあげることができる。
2
主要な定義 以下では、主要な定義について解説する。なお、簡単のため厳密な数学的な定義に
は一部触れない場合がある。
2.1
選好順序・効用 ある結果𝐴と、ある結果𝐵が存在し、あるプレイヤー𝑖にとって、結果𝐵より結
果𝐴のほうが好ましい（より望んでいる）ことを、
𝐴 ≻! 𝐵
と書く。このとき、𝐴, 𝐵の関係（二項関係）≻! のことを、選好順序という。
また、任意の 2 つの結果𝑆, 𝑇に対して、
𝑆 ≻! 𝑇 ⇒ 𝑓! 𝑆 > 𝑓! (𝑆)
となる、値として実数をとる関数𝑓! を定義する。この関数𝑓! を、プレイヤー𝑖の効
用関数と呼ぶ。
□例：昼ごはんの選択
A さんは、お昼ごはんに、うどんか、そばか、ラーメンを食べようと思ってい
る。そばよりもうどんのほうが、うどんよりラーメンのほうが食べたいと考えて
いる時、二項関係≻! を用いて、
うどん ≻! そば , ラーメン ≻! うどん
と書ける。また、関数𝑓! を以下のように定める。
𝑓! うどん = 10 , 𝑓! そば = 5 , 𝑓! ラーメン = 20
このとき、関数𝑓! は、A さんの効用関数になる。
もちろん、A さんの効用関数を、
𝑓! うどん = 1 , 𝑓! そば = 0 , 𝑓! ラーメン = 2
と定めても良い。
2.2
提携形ゲーム 提携形ゲームとは、
(𝑁, 𝑣)
である。より具体的に、𝑁とはプレイヤー全体の集合（𝑁 = {1,2, … , 𝑛}）、𝑣とは、
任意の提携𝑆を引数にもつ、引数にとった提携の全員により獲得する総効用関数
である。
ここで、提携𝑆とは、𝑁の任意の空でない部分集合のことである。
□例： ３人のバイト代
A さんと B さんと C さんがバイトをしている。各個人がそれぞれ別の仕事を
すると、それぞれ 1000 円を得ることができる。2 人で協力して作業に取り組め
ば、その 2 人で合わせて 2500 円を得る。3 人で協力すれば、3 人で合わせて 5000
円を得る。
こ の と き 、 𝑁 = {𝐴, 𝐵, 𝐶} で あ り 、 考 え ら れ る 提 携 は 、
𝐴 , 𝐵 , 𝐶 , 𝐴, 𝐵 , 𝐵, 𝐶 , 𝐶, 𝐴 , {𝐴, 𝐵, 𝐶}の 7 つである。ここで、𝑣を、
𝑣 𝐴
𝑣 𝐴, 𝐵
=𝑣 𝐵
= 𝑣 𝐵, 𝐶
=𝑣 𝐶
= 1000
= 𝑣 𝐶, 𝐴
𝑣 𝐴, 𝐵, 𝐶
= 2500
= 5000
とすると、(𝑁, 𝑣)は提携形ゲームである。
2.3
配分 これ以降、以下の性質を満たす提携形ゲーム(𝑁, 𝑣)を考える。これは、各プレ
イヤーが積極的に協力しようとすることを前提としたゲームについて、考察する
ためである。
□優加法性
任意の提携𝑆, 𝑇に対して、以下が成り立つ。
𝑣 𝑆, 𝑇 ≥ 𝑣 𝑆 + 𝑣 𝑇
提携形ゲームの結果、各プレイヤーが得る効用を並べたものを、効用ベクトル
𝑥 = (𝑥! , 𝑥! , … , 𝑥! )と呼ぶ。ここで、効用ベクトルが配分であるとは、
∀𝑖 ∈ 𝑁: 𝑥! ≥ 𝑣({𝑖})
𝑥! = 𝑣(𝑁)
!∈!
の 2 条件を満たすことである。これは文字通り、ゲームが行われた後に、各プレ
イヤーに効用が配分された時に、その配分された効用の、効用ベクトルが満たす
（満たされているべき）条件である。
1 つめの条件は「個人合理性」と呼ばれ、１人で行動したときが、最も低い効
用になってしまうことを示している。また、2 つめの条件は「全体合理性」と呼
ばれ、これは配分された利得の合計が𝑣(𝑁)と一致することを示している。優加法
性より、効用ベクトルの和
!∈! 𝑥! は、𝑣(𝑁)より大きくなることはないため、全体
合理性は、全体で協力することで、最大の利得を獲得していることを示している。
2.4
支配・コア 提携𝑆において配分𝑥が配分𝑦を支配するとは、
∀𝑖 ∈ 𝑆: 𝑥! > 𝑦!
𝑥! ≤ 𝑣 𝑆
!∈!
の 2 条件を満たすことである。このとき、𝑥 dom! 𝑦と書く。また、提携𝑆を省略
し、単に「配分𝑥が配分𝑦を支配する」ともいい、𝑥 dom 𝑦とも書く
□例：３人のバイト代の不満
A さんと B さんと C さんがバイトをしている。各個人がそれぞれ別の仕事を
すると、それぞれ 1000 円を得ることができる。2 人で協力して作業に取り組め
ば、その 2 人で合わせて 2500 円を得る。3 人で協力すれば、3 人で合わせて 5000
円を得る。
こ の と き 、 効 用 ベ ク ト ル 𝑥 = (1700,1700,1600) と 、 効 用 ベ ク ト ル 𝑦 =
(3000,1000,1000)は共に配分である。しかし、仮に配分𝑦が実行された時、B さ
んと C さんは以下のような理由で正当な反論を行うことができる。
ü
私たちは、配分𝑦より配分𝑥のほうが取り分が多い。
ü
配分𝑦において、私たちの効用の合計は 2000 だ。
ü
もし B と C の 2 人だけで協力したならば、2500 の効用を得ることが
できる。
ü
よって、配分𝑦における私たちの取り分は少なすぎる。
ここで、提携{𝐵, 𝐶}において配分𝑥は配分𝑦を支配することは自明である。
支配される配分とは、何らかの提携が存在し、その提携が正当な反論・文句を
つけることができる。よって、何にも支配されない配分は、優れている配分だと
考えることができる。そのような配分を考察するのが「コア」である。
ここで、配分𝑥がコアであるとは、
∀𝑦 ⊂ 𝑁: ¬( 𝑦 dom 𝑥)
を満たすことである。つまり、配分𝑥がコアならば、他のどんな配分にも支配さ
れないことを示している。
3
ケーススタディ 3.1
ケースの前提条件についての補足 前章において主要な定義を述べた。まずはじめに効用関数や、提携形ゲームと
はなにかを定義した。その後、効用ベクトルが配分であることの定義、配分にお
ける支配関係、コア、を順に定義した。
ここで着目したいのは、支配関係の定義に配分が利用されていることだ。しか
し、その定義には特別配分を用いる必要性はなく、その代わりに効用ベクトルを
用いても、自然な定義ができる。以下のケースでは、𝑣(𝑁)、つまり、全員が協力
した場合にどれ位の効用を得ることがよくわかっていない場合を考えている。
𝑣(𝑁)がわからないということは、どの効用ベクトルが配分なのかがよくわからな
いということである。
以下、支配関係とは、配分ではなく効用ベクトルによって定義されるものとす
る。
□効用ベクトルによる支配関係の定義
提携𝑆において効用ベクトル𝑥が効用ベクトル𝑦を支配するとは、
∀𝑖 ∈ 𝑆: 𝑥! > 𝑦!
𝑥! ≤ 𝑣 𝑆
!∈!
の 2 条件を満たすことである。
3.2
結婚定理 3 人の男性 m1,m2,m3 と 2 人の女性 w1,w2 がそれぞれ結婚相手を見つけよう
としている。どの人も、独身でいるよりも結婚する方を好むとする。男性と女性
の選好順序は表 1 および 2 で与えられる。
w1
w2
m1
m2
m3
1位
w1
w1
1位
w1
w1
w2
2位
w2
w3
2位
w2
w2
w1
3位
w3
w2
表 1
表2
ここで、選好順序を利得とし、ある人において結婚相手が選好順序 1 位の人で
ある場合は 3 点、2 位の人である場合は 2 点、3 位の人である場合は 1 点、結婚
できない場合は 0 点を獲得できるとする。
実現可能なカップルの組み合わせは、以下の 6 通りである。ただし、同列の男
性と女性が結婚するとする。
𝑎=
𝑑 =
𝑚1 𝑚2
𝑤1 𝑤2
𝑏=
𝑚1 𝑚2
𝑤2 𝑤1
𝑐=
𝑚1 𝑚3
𝑤1 𝑤2
𝑚1 𝑚3
𝑚2 𝑚3
𝑚2 𝑚3
𝑒 =
𝑓 =
𝑤2 𝑤1
𝑤1 𝑤2
𝑤2 𝑤1
一般に、2 つの異なるグループからなるペアの組み合わせを、マッチング
(matching)という。男性 3 人と女性 2 人の結婚問題の例では、全頁のように 6
つのマッチングが可能である。
それぞれのマッチングにおける、各人の利得ベクトルは以下のように表され
る。
𝑁 = {𝑚1, 𝑚2, 𝑚3, 𝑤1, 𝑤2} 𝑎 = (3,2,0,3,1) 𝑏 = (2,3,0,2,3) 𝑐 = (3,0,3,3,2) 𝑑 = (2,0,2,1,3) 𝑒 = (0,3,3,2,2) 𝑓 = (0,2,2,1,1) マッチング間の支配関係について述べる。支配の定義は以下の通りである。
提携 S において X が Y を支配する時、
𝑋 𝑑𝑜𝑚! 𝑌 ↔ 1. 𝑣(𝑆) ≥ ! 𝑋! !∈!
2. 𝑋! > 𝑌! (∀𝑖 ∈ 𝑆) マッチング𝑎は、男性 m1 と女性 w1 の提携によって実現可能である。
𝑎 𝑑𝑜𝑚 !!,!! 𝑏 であるとすれば、支配の定義より、以下の式が成り立つ。
𝑎 𝑑𝑜𝑚 !!,!! 𝑏 ↔ 1. 𝑣(𝑚1, 𝑤1) ≥ 𝑎!! + 𝑎!! 2. 𝑎!! > 𝑏!! ∧ 𝑎!! > 𝑏!! マッチング𝑎において、1. 𝑣(𝑚1, 𝑤1) ≥ 𝑎!! + 𝑎!! の左辺はm1の利得とw1 の利
得を足した総利得であるため、6となり、𝑎!! および𝑎!! はそれぞれ m1 と w1 の
利得であるため、右辺は3 + 3である。よって、6 = 3 + 3となり、1 が成立する。
また、マッチング a および𝑏において、𝑎!! > 𝑏!! は、3 > 2、𝑎!! > 𝑏!! は 3 >
2 より、2 も成立する。よって、m1 とw1の提携においてマッチング𝑎はマッチ
ング𝑏を支配する。
他の支配関係についても、以下のことが言える。
𝑐 𝑑𝑜𝑚 !!,!! 𝑎
𝑎 𝑑𝑜𝑚 !!,!! 𝑑
𝑎 𝑑𝑜𝑚 !!,!! 𝑒
𝑎 𝑑𝑜𝑚 !!,!! 𝑓 支配関係を図 1 に示す。
b c
d a
e f 図1
図 1 より、c 以外のすべてのマッチングはコアに属さないことが言える。ここ
で 、 𝑋 𝑑𝑜𝑚! 𝐶 となる 𝑋, 𝑆 の存在を仮定する。 支 配 の 定 義 の 2 よ り 、
∀𝑖において𝑋! > 𝐶! が成立するため、𝐶!! = 2 であるw2に対して𝑋!" > 𝐶!" とな
る。このためには、S =(m1,w2)が必要であるが、X !" < C!" となり、定義の 2
が成立せず、矛盾する。よって、X は存在しない。以上のことから、C はどのマ
ッチングにも支配されないことが言える。つまり、マッチング C はコアに属す
る。
結婚問題のコアが非空であることは、1962 年に Shapley によって証明された。
結婚問題のゲームモデルは、病院によるインターンの採用や、労働市場の分
析等に幅広く応用されている。
4
参考文献 岡田章 (2011) 『ゲーム理論』有斐閣．