-
Hanpen_nepnaH
- 1473
- 0
- 0
- 0
-
- いいね！0
Lucas KBYS
@lkbys
繰り返し型の囚人のジレンマに関する論文 http://t.co/jkVr7Ujl をざっと読みました。かなり端折られていて、チェックすべきところばかりで大変そうです
2012-12-11 23:04:19
Lucas KBYS
@lkbys
囚人のジレンマのプレイヤーの2人を、XとYとします。それぞれc (cooperation) とd (defection) の2つの選択肢があります。2人それぞれ意思決定して同時に公開。Xから見れば (Xの決定, Yの決定) = (c,c), (c,d), (d,c), (d,d)
2012-12-11 23:14:55
Lucas KBYS
@lkbys
うっかりこの論文と違う記法を使ってしまいましたが、こういう書き方でなく、ccやddのように、くっつけて書いています。それに合わせましょう
2012-12-11 23:18:36
Lucas KBYS
@lkbys
この囚人のジレンマを繰り返すことを考えます。論文の前半で計算されているのは、これをマルコフな過程とみた計算です。Xは、ccだった場合に確率p_1でcを選び確率(1-p_1)でdを選ぶ、cdだったら……、という4つの確率を、事前に決めておくのです
2012-12-11 23:31:35
Lucas KBYS
@lkbys
これは、何回繰り返したあとであっても直前の1回の情報しか参照しないで次回の手を決定する、ということですから、思い切った単純化にも思えますが、それより前の情報まで参照したとしても、より良い結果にならない、という証明があるようです。まだ読んでいませんけど……
2012-12-11 23:35:41
Lucas KBYS
@lkbys
XとYがこの確率p_i (i=1,2,3,4) とq_i (i=1,2,3,4) を決めると、4通りの結果xyのそれぞれに対して、その次の回にどの結果がどれだけの確率で生じるか、が求まります（単なる確率の積です）。例えば、cdの次回にdcになる確率は (1-p_2) q_3 です
2012-12-11 23:42:06
Lucas KBYS
@lkbys
この16個の確率を4×4行列に並べてMとします。ベクトルは横に並べて書く（ことになっているようです）ので、それに合わせて並べます。Mは固有値に1を持ちます
2012-12-11 23:48:09
Lucas KBYS
@lkbys
M'の余因子行列をAdj(M') と書きましょう。線形代数の知識から、Adj(M') M' = O が成り立ちます。ここから、Adj(M') のすべての行は v と平行であることがわかります
2012-12-11 23:56:13
Lucas KBYS
@lkbys
……というところまででも、「このマルコフ過程は本当に収束するのか」「M'の解空間は本当に1次元しかないのか」と、気になるところがあるわけですけど、先に進みます
2012-12-11 23:58:24
Lucas KBYS
@lkbys
R^4の元 f に対して v との内積を返す線形写像 R^4 → R がありますが、Adj(M') の4番目の行を v の代わりに使って、代用の線形写像を作ります
2012-12-12 00:02:51
Lucas KBYS
@lkbys
Adj(M') の定義から、その4番目の行は、M' の1列目から3列目で決まります。(i,j)-小行列式に (-1)^{i+j} を掛ける、例のあれです
2012-12-12 00:07:46
Lucas KBYS
@lkbys
Adj(M') の4行目と f の内積は、M' の4列目を f に換えた行列のdet であることがわかります。detですので、1列目を2列目と3列目に足しておいても、値には影響しません。
2012-12-12 00:12:37
Lucas KBYS
@lkbys
1列目を2列目と3列目に足して何が起こるかと言うと、2列目にはYの戦略 q_i がまったく影響しない、3列目にはXの戦略 p_i がまったく影響しない、というきれいな行列式になります
2012-12-12 00:15:12
Lucas KBYS
@lkbys
この行列式の値はpとqとfで決まるので D(p,q,f) と書きます。これはAdj(M') の4行目と f の内積であり、Adj(M') の4行目は v と平行ということでしたから、D(p,q,f) / D(p.q.1) で、v と f の内積そのもの、になります
2012-12-12 00:21:12
Lucas KBYS
@lkbys
あ、さきほどの D(p,q,1) において 1 と書いたのは、1を4つ並べた縦ベクトルです。vは4つの成分の和が1なので、こういう規格化になるわけです
2012-12-12 00:25:49
Lucas KBYS
@lkbys
このマルコフの収束先 v におけるXの利得は、 S_X = (R,S,T,P) と置いて、これと v の内積です。つまり、D(p,q,S_X) / D(p,q,1) です。同様にYの利得は D(p,q,S_Y) / D(p,q,1) です（ただしS_Y = (R,T,S,P) ）
2012-12-12 00:27:20
Lucas KBYS
@lkbys
XとYの利得をそれぞれ s_X と s_Y と書きます。任意のαとβとγに対して α s_X + β s_Y + γ = D(p,q, α S_X + β S_Y + γ 1) / D(p,q,1) が成り立ちます
2012-12-12 00:31:23
Lucas KBYS
@lkbys
ここでようやく、D(p,q,f) の定義の際に2列目と3列目に施しておいた細工が効いてきます。 D(p,q, α S_X + β S_Y + γ 1) は行列式ですから、2列目と4列目が同一のベクトルであるとき、値が0になります。そして、2列目はXの戦略 p_i のみで決まります
2012-12-12 00:36:22
Lucas KBYS
@lkbys
つまり、2列目ベクトルが α S_X + β S_Y + γ 1 であるように X が p_i を定めてやりさえすれば、α s_X + β s_Y + γ = 0 が成り立ってしまうわけです
2012-12-12 00:39:31