ゲームの有限化

(1)

ゲームの有限化

奥田英輔

1.はじめに

本稿はAumann (1974)の結果を有限化する。有限化の方法としては種々の方法があるが本稿では大数の法則を用いる。中心極限定理を用いればより精度の良い有限化ができるであろうが(Mas‑Colell (1978)およびOkuda and Shitovitz (1985)参照),有限化,確率化するためには大数の法則で十分である。測度のconvexity (Lyapunov (1940))を使わないで大数の法則を用いて有限化する。本稿はAumann (1974)を読まれているものとして書かれている。

2.定義と定理

(2.1)定義. eventAが￡>0に対して¥pi(A)‑ Pj(A)¥<eforali i,j∈N であるときe‑ objectiveであるというo

(2.2)定義.虜をrouletteとする a>0とし, Mを正整数とする, P(顔, M,a)とはOのpartitionであり,その各元Aが92に含まれて,元の個数は Mであり, a≧少,(A) foralli∈NandforallA∈P(顔, M,a)であるようなも

のである。

(2.3)補助定理・ 91をrouletteとするO任意の正整数Mを与えるとPirn, M¥An

M'] が存在する。ただし, 〟'≧〟である。

(証明) 97のnon‑atomicityから0のfinite partitionP'があって, A∈P'は Aざ97で仙)≦+MであるようなものがあるMaxi∈N少,‑(A)‑0であるようなAはMaxi。atA(A)>0であるようなAと合併させる。もちろんA∈P'は A∈97で0 < Maxi∈ Pi(A)≦+Mであるoこのような有限個のAを以下のよ

(2)

うに一列に並べる。

.11， .12，

そして順次左から合併して行き，合併したものを.1'とする。

MaXieN Pi(s' )ミ=2M 1

になったら合併を中止する。すると

一2 ムLM=~'~~""'E1V 亘M似仇a.x L" ，... / = 1凶

である。

以上の手順をくり返すと，最後にはP'の元が尽きても MaxieNお(.1')くであるようなものができる可能性がある。それも partitionの元と考え 2M

て，上の手順でQの一つのpartitionP"^{ができる。} P"^の元でMaXieNPi(s)

~ 2 ^̲M¹.^̲..^{であるものの個数は}. LAJ ~aJ U ....../""./ 1 1t!.I~'o... ^M‑'F^a.A. .^X.. AtEN ⁱ^e^N^ρ(Yt \~J .1)くであるものの個数より大で.......... 2 M あるか等しい。それは MaXieNPi (.1)くであるものの個数は高々 lであ

2M るから.

P"の元の個数を M'とすると，M三Mである。明らかに MaXieNρ;(.1)

は L1/2M;:::三MaxieNあ・(.1)豆 1〆M 112M

~L 1/2M豆M似ieN お(.1)豆 1/M

̲M'

= 2 2M 4 n~ 1

一一三ーミお(.1) 証了。

. M'=M

(2.4)補助定理.況をrou1ette，B 1 ，・，Bnを・・ events，0くαく1，え>1とする。正整数M と，_{P(~ ，} M.一一)が存在して，その中から4n L=(MαJ*個

' M

の元の組をとり出すと 1‑去より大きい比率で lぇ=ηα(4 n) ~ . 1

￨

α・あ(si)ーあ(Ansi) I 豆~^ ，."，，¥.，./ +ー

=v M 'M

*C Jはガウス記号である。

(3)

である。ただし，AはL 個の元の和集合である。

証明。補助定理 (2.3)から正整数M とP(f'A，κt芳f)^{が存在し口て，}

t

芳f^孟訪^ρ^おⁱωω) 伽fO町r川川al比 Na刷凶nl凶d吋凶(惚g， M， jf )

である。

目i(si)

qi(l1) =お(11n:.si)一守ムとおくと

‑上豆あ(11nßi・)一色笠l~ ~竺_{M = M}

!qi(l1)凶器

すべての11EP(!Jl， M， !4n i)^{に番号をつけて}

111 ，・・・，11M とする。すると

qi(111 ) +…+qi(I1M) = 0 である。

T=(T1，…， TL)は111，… ， 11M から L 個の組合せをとる変数とする。 ~T は組合せについての和を表わす。

q( わ 2=~?=I{qi(T1) +…+qi(TL)} 2， V(qi， M， α)=JrZT{qi(Tl)

MしL +…+qi(TL)} ²， v= ~?= 1 V(qi， M， α)

とおく。今から大数の法則の基礎である Tchebychevの不等式に相当する不等式を導く。

u=Jrh(T)2

MしL

=か^T^，^q⁽^T^q(T)2⁾^'²^'^>^.^.^<²^V^.^.⁺^L^‑;CL~T， ^.^l

>‑LZ A2U uCL~T， q(T) 2.>..<2V

q(T) 2

q(T) 2豆..<2V

(4)

=A2u‑‑Lz

~L~T. q(T) 2 >A2V

法志戸Z戸zむT，qJAふ(4^あJ^'⁾²^>刈^μ^A^2V，比 T の例うち吠で吋qρ(σ即T 数の比率であるo

1 ̲ 1 ~ ....... ，?

:. A‑2 >京子^T^.^q('.I') 2 > A 2 V

̲ 1 ~ ̲ / ' 7

(2.5) .・.1一万く宗主1:r. q(T)2豆え 2V 以下で Uの評価を行なう。

V

附(匂切q釘j.ιMh 」↓「占エ&日T孔刈巾{匂切q酌qj(T似バ(σ引T1)川+...+句叩^q豹j(仇T九勾L川ρけω}) MVL

ここで

=↓1:r(qj(T 1) 2 +... +qj(TL) 2

MしL

+qj(T 1) {qj(T 2) +…+qj(TL) }

+qj(TL) {qjCT1) +…+qj(TL^ーd}J

( 4 n) 2

1:r{qj(T 1) 2 +…+qj(TL) 2} く ~L ・ L"ji;

である。

一般性を失うことなく

1:7flj(T 1) {qj(T 2) +・・・+qj(TL)}

について考える。たとえば T1=Aぃ T2=A2と固定した場合を考えると M‑2CL‑2qj(Al){qj(A2) +…+qj(AM) }

= ^{‑ M ‑2}C^L‑2・qj(Al)2

.

・.1:r(qj(T1){qj(T2)+…+qj(TL)} +………+qj(TL) {qj(T1) +…

+qj(TLー1)}J

=‑M‑2C_Lー 2 {qj(Al)2+…+qj(AM) 2}豆O 故に

( 4 n) 2 α ( 4 n) 2

V(qj. M， α)豆L.'M; ~玉故に

......nα( 4 n) 2 U孟

M

(5)

AをL個の元の和集合とする。 (2.5)から 1‑去より大きい比率で

￨

か^i(B^け ⁱ^伽 ^Bⁱ⁾¹^針^l.Pηα(4ⁿ⁾^~

である。

￨

αお(Bi)‑Pi(A nBi) 1

= laPi(Bi) ‑MPi(Bi) +MPi(BL り‑Pi(AnBi)1

Z玉￨ゆi(Bi)一::..Pi (B i) 1 + 1 _ML ~A" Pi (B i) ‑Pi (A n B i) 1

=1α M￨・お (Bi)+IMPi(Bi) ‑Pi(AnBi) L 1

̲̲ 1 ^I I.{~ n α( 4 n) 2

=M・ M ^証了。

(2.6)系.!Jlをroulette，B 1 ，… ，snをevents，0くαく1，_~>0とする。

すると eventA e!Jlが存在して

￨

αお(Bi)‑Pi(A nBi) 1くEである。

(2.7)系.況をroulette，B 1 ， Blをevents，Oくαく1，~> 0とする。

すると eventAe況が存在して， α1‑Pi(A) 1 く~すなわち A は ~-objec-2 tiveで，

￨

αお(Bj)ーあ(AnBj) ¹く!for i= 1 ，… ， n， j= 1，… ， 1である。

2

証明. (ρ1 (Q)，… ， Pn (Q)，ρ1 (Bl)，…， Pn (B 1)，…， ρ1 (Bl)，…，九 (Bl) )

=(1，… 1 ，ρ1 (Bl)，…， Pn(Bl)， ρ1 (Bl)，…， Pn (Bl))に対して

系(2.6)を適用する。証了。

(2.8)補助定理.jeNとし，ajをSjの分布とする，E> 0に対して，jは

~-objective mixed strategy Sjですべての SjeSjに対して IPi(Sj=巧)ーσ'/Sj)¹くE

であるものをもっ。

証明.σj'(Sj)> 0なるごりの元号の数 mに関する帰納法による。

BljをAssumptionII (Aumann 1974)によるj‑secretなrouletteとする。

するとつぎのことが証明される。

(6)

(2.9) strategy S1が補助定理 (2.8)に従うように選ばれることができるとすると， events {Sj=Sj}はotjにある。

m=lのときは明らかである。 m>lとし，m‑1に対して上のことが真であるとする。

Sj= {si，…， s，^m，…}とする。ただし，kくm のとき，そしてそのときだけσ'j(S/)> 0 とする。帰納法の仮定により互いに素な ~-objectiveevents B 1 ，

B mー 1で ltj(Bk)‑σ'j(号f)/(1 ‑σ，/令fI))1くEであるようなものがある。

系 (2. 7)において ~=øti とおけば B1 ， … ， ßm-1 と独立な ~-objective

j‑secret event smで￨あ・(sm)ー (1‑σ'j(Sj)) ¹くEであるようなものがある。

hくm に対して Ak=Bknsm，Am=Q¥ sm， k>mに対して Ak=ゆとおけばすべてのhに対してA匂勿jである，SjをS/ω)=s/ if and only ifωεAkと定義する。すると Sjは (2.9)を満足する。証了。

(2.10)補助定理 (Aumann(1974))(ι …， Sn)をn個のstrategiesの組とし， seSとする。そこで，ある ieNを除いては，すべての Sjはmixed であるとする。すると

お{S=S}=お{Sj=Sj}釘{Sj=Sjfor all j* 1 }

=ρj{S=S 1}…あ・{Sn=Sn}

(2.11)系 (Aumann(1974).(S1， Sn)はn個の mixedstrategiesの組であるとする。すると S;は互いに独立である。

(2. 12)定理.Nash equilibrium payoffsの集合は， _~‑objective mixed equi1ibrium payoffsの集合と一致する。

証明.証明は Aumann (1 974) と objective を~‑objectiveに置きかえるだ

けで同様にできるので省略する。証了。

(2. 13) 定義.集合 W が~> 0 に対して ~-convex であるとは o く α く

lとWの元ぁ yに対して Wの元zが存在して

Iz‑αxー (1‑α) ylくE

となることである。

(2.14)定理.public roulette 況が存在すると仮定する。すると equi1ibrium payoffsの集合と feasiblepayoffs の集合は ~-convex である。

(7)

証明.最初に equilibriumpayoffsについて考えるo~を public rouletteとする。 ~>O ， ..(>1， 0くαく1とする。補助定理 (2.4)においてρ1(A)，…，

Pn(A) を考える。~> 0 に対して，正整数 M と P(~ ， ^{M，与)が存在して，}

その中からL個の元の組をとり出してその和集合をAとずると1ーがり大きい比率で￨α‑pj(A)IくEであり，AE~ であるから， {Sl=Sl， …} ， {ι

=Sn}とそれらから生成される eventsに対して独立である。

各playerがplayする strategyηをつぎのように定義する:もしAが起こったらSjをplayし，そうでなければtjをplayする。云い換えればiは与えられた pureSjESjを

(2.15) [A n {Sj=Sj} ] U [(Q¥A)円{tj=Sj}]

が起こったとき，そしてそのときだけ playする。すると (2.15)はσ‑field 仇に含まれるから strategyである。 rがequi1ibriumpointであることは容易に証明される。

h=MaxsESlh(s) I

とする。 {Sl=S 1}，… ， {tn=Sn}から生成される Qのpartitionを考えると Aはそれらに対して独立であるから

￨

αH(s) + ( 1 ‑α)H(t) ‑H(r) I く~ h

であることがわかる。 M を大きくとれば上式の右辺はいくらでも小さくなるからこれで証明された。 feasiblepayoffsの集合の convexityについても

同様である。証了。

3 . 結び

sect.2では Aumann(1974)を大数の法則により有限化，確率化する道筋について述べた。全面的に有限化するには Q を有限集合として各勿iについて補助定理 (2.3)，(2.4)，系 (2.6)，(2. 7)を参考にして条件を与えればよい (Aumann(1987)参照)。

(8)

参考文献

Aumann， R. ].(1974) Subjectivity and Correlation in Randomized Strategies，" J ounna1 of Mathematical Economics， 1， 67 ‑96.

Aumann， R. ]. (1987) Correlated Equi1ibrium as an Expression of Bayesian Rationa1it‑ y，" Econometrica， 55， 1 ‑18.

Lyapunov， A.(1940) Sur les fonctions‑vecteurs complement additives，" Bull. Acad. Sci. VSSR Ser. Math. 4， 465‑478.

Mas‑Colell， A. (1978) A note on the core equiva1ence theorem : How many blocking coa1i‑ tions訂ethere?" Journa1 of Mathematica1 Economics， 5， 207ー215.

Okuda， H. and B. Shitovitz， (1985) Core Allocations and the Dimension of the Cone of Efficiency Price Vectors，" Journal of Economic Theory， 35， 166ー171.