数理解析研究所講究録 1461 巻 2005 年 214-224

214

Stochastic Game の開放型 Tree Queuing
Network への応用
早稲田大学・商学部

理工学部

数学・応用数学研究所

毛利 裕昭 (Hiroaki Mohri)
School of Commerce, Institute of Pure and Applied Mathematics$\rceil$.

はじめに

ここでは,グラフが木構造をもった計算機ネットワークの制御に確率過程ゲーム (Stochastic Game) を璋用することを考える. 確率過程ゲームについては, Mertens(2002), Vieille(2002), Raghavan and Filar(1991) がサーベイ論文としては便利である. 関連書籍としては, Filar and Vrieze1996) がある.
$\langle$

Mohri(2005) では, 有限個の並列待ち行列のスイッチングの問題についてAltman(1996) に沿った考え方に基づき, モデルを記述して定常状態および有限ステージでの最適方策 (ゲームの戦略) について考察した.

Network=計算機ネットワークとは, 待ち行列ネットワークを指すものとする. 待ち行列ネットワークの確率的解析に関しては, フィ
ここでの–ドバックがあるタイプも含め様々なネットワーク構造の解析がすでに行われている. 特に定常状態の解が積形式解の形になる場合と条件について深く研究が進められている.
ここではネットワークの客の振り分け制御に確率過程ゲームを用いる.
確率過程ゲームは, 非協力ゲームにおける繰り返しゲームを精緻化したものである. それ故, プレイヤーの立場, 戦略といった設定を明確にする必要がある. しかし, クローズしたネットワークの中のフロー (客の流れ)や, 部分的にオープンであってもフィードバックのある場合はそのネットワークの内部のコントロールする主体の設定が困難であるためここでは,木構造に限った分析を行う.

215

2.
2,対象とする待ち行列ネットワークに関する考察
木構造ネットワーク$\rceil$

本稿で対象とするのは木構造ネットワークである. ただし, 下記の右図のような場合を考慮しない. 頂点 (根) から要求 (客) が出され, それが階層的な構造を経て流れていくような場合を対象とする. つまり, 下記の左図のような根つき木 (二重丸になっているノードを根とする) の階層構造になるものを対象とする. (勿論位相幾何学的には右図もあるノードを根として, 根つき木として書き換えることはできるが, すべてのノードが同等なものは取り扱わない. )2. 2木構造の待ち行列ネットワーク

上記で考えるノードは待ち行列ノードであり. 階層を経るにつれ下位層に複数のノードがあれぼ, 客の振り分け制御を確率過程ゲームで行う. ここでは, 振り分け制御の結果ネットワーク全体が定常状態となる場合のみの考察を行う. 待ち行列の研究の立場からは, フィードバックがある部分的, もしくは全体的にクローズされたネットワークが興味深い.
ここでは,しかし,制御問題になると困難を伴うためあえてこのような単純なネットワークを対象とする.

218
2. 3 木構造待ち行列から直列待ち行列への分解
木構造待ち行列ネットワークで根と根以外のあるノードを特定する. すると,根からそのノードまではグラフが木であるためパスが 一に決定される.

したがってその間は直列待ち行列 (Tandem Queues) となる. また, そ$\beta\not\in$の特別なノードを含みそれより下の階層の部分グラフにおいてまた別のノードを指定すれば同様に直列待ち行列である.
ここでは, 直列待ち行列の重要な性質について,レビューをする.

このような直列待ち行列では, 最初の待ち行列の出力過程が, 第二の待ち行列の入力過程になる. 解析の為, 以下のような仮定をおく。 すべて最初の待ち行列に関するものである.
入力過程はパラメータ のポアソン過程
サービスの確率過程はパラメータ の指数分布にしたがう$\lambda$

$\mu$

.
.

$\rho:=\lambda/\mu$$\mathrm{X}_{\mathrm{a}}$: 到着間隔を示す確率変数: サービス間隔を示す確率変数: 出力間隔を示す確率変数: 待ち行列にいる顧客数を示す確率変数.
.
. 上記の確率変数に対しては, すべて確率密度関数が存在しそれは$\mathrm{X}_{\mathrm{S}}$$\mathrm{X}_{\mathrm{d}}$$\mathrm{Y}_{\mathrm{Q}}$$\mathrm{f}_{\mathrm{X}}^{\backslash }(\cdot)$のように確率変数を添え字とする記号で表すものとする.

これはいわゆる$\mathrm{M}/\mathrm{M}/1$でもっとも単純な待ち行列である.

さて,2 番目の待ち行列の入力過程は最初の待ち行列の出力過程であることは明らかである。 以下その為の解析を行う.
最初の待ち行列から客が出てきたとき, 「次の客がすでに待ち行列に待機しておりすぐにサービスされる場合」 (Case 1) と, 「次の客が待ち行列にまだいない場合」 (Case 2) があり, 次の 2 つの式が得られる.
(Case 1)
$P(X_{d}\leq t1\mathrm{Y}_{q}\neq 0)=P(X_{s}\leq t)$(Case 2)
$P(X_{d}\leq t|\mathrm{Y}_{q}=0)=P(X_{a}+X_{s}\leq t)$217

ここで,関数 $f$ のラプラス変換が存在するとき,:f のラプラス変換,((s) は省略することもある)$L(f)(s)$と書くことにする. ラプラス変換の線形性を利用し, (Casel) の待ち行列に客がいる確率は で, すると (Case2) の場合は $1-\rho)$ の確率で起きることは明らかなので, 以下の式が成り立つ.
$\langle$$\rho$$L(fi_{d})=(1-\rho)L(fi_{a})L(ff_{s})+\rho L(fi_{s})-(*\rangle$

指数分布のラプラス変換より$L(*h_{a})= \frac{\lambda}{\lambda+s}$

これらをる.

$\langle$$*)$$L(fx_{s})= \frac{\mu}{\mu+s}$

またに代入して計算する.

$\text{定}\ovalbox{\tt\small REJECT}$より$\rho=\frac{\lambda}{\mu}$

力 ,$\grave{\grave{3}}$$(*)= \frac{\lambda}{\lambda+s}$

F 純計算によって得られ

この逆ラプラス変換は指数分布であるので, 最初の待ち行列の出力過程はポアソン過程である. 2 番目の待ち行列の入力過程もパラメータが同じポアソン過程となる。 直列待ち行列ネットワークにおける最初の入力過程がポアソン過程であれば, 指数サービスの待ち行列が連なっている場合,どの待ち行列においても入力仮定は同じパラメータのポアソン過程となることがわかる.

2. 3 木構造待ち行列再考
木構造待ち行列を前節の考察をもとに再考することにする. 本稿では客の振り分けについて確率過程ゲームによる制御を行うがネットワークの全体としては, 定常状態におかれていることを仮定している.

この仮定によって, ある待ち行列に対して一階層下の待ち行列が 個あ番目に振り分けられる確率分布るときに, 制御の結果 1 番目から番目の待ち行列に対する入力は,が存在する. すると,$\mathrm{k}$$\mathrm{k}$$(p_{1},\ldots, P_{i},\ldots, p_{m})$元のポアソン過程の指数分布に$\mathrm{i}$$P_{j}$を掛けたものに他ならない.

218
3.

確率過程ゲー$\Delta$(Stochast$\dot{1}\mathrm{C}\mathrm{G}\mathrm{a}|\mathfrak{n}\mathrm{e}$) についての予備知識

確率過程ゲーム (Stochat ic Game) は, ゲーム理論の標準的テキストに解説が記述されていることはほとんど無いため, ここで必要事項をMertens(2002) に従って記す.

3. 1$\bullet$$\bullet$$\bullet$$\bullet$

確率過程ゲームの為の定義
状態空間 ; 可測空間
プレイヤー ;

$J$$(_{-\cdot-}\Omega_{-----},A..\Lambda$(L よ可算有限集合とする)\in 7 。アクション空間 : 可 」ゆ。
全アクション集合 ;プレイヤー$\mathrm{L}S^{i}\mathrm{S}_{-}^{i})\underline{)}$$ffl\mathrm{I}$$/\cdot$$S= \prod S^{i}$$i\in I$$\bullet$

推移確率 ;$\underline{P.\cdot\Omega}\underline{\cross}S_{---}\underline{arrow\Omega}_{-}|$$P(A|\omega, s)$$\bullet$

where $A\in A,$$\omega\in\Omega,$$s\in S$

利得関数ベクトル ;$i\in J$ か
これは下記で述べる各プレイヤーの利得関数ら構成されるベクトルである,ゲームの初期状態 ;(ここで離散時間で考える) の状態 ;ゲー の時間(時間の各プレイヤー
プレイヤーはアクションベクトル:のアクションなのでベクトルであることに注意) を同時に選択すを利得として受け取り,る. そのとき各プレイヤー嫁よ,遷移確率に従って移る.
この章では, 上付き添え字がプレイヤーになっており, 下付き添え字が時間に対応している. 後に が現れるがこれは時間 での利得関数ベクトルの意味である.
$\mathrm{g}(\omega, \mathrm{s})$$\mathrm{g}^{i}(\iota v, \mathrm{s})$$\bullet$$\bullet$$\bullet$$\omega_{1}$$\text{ム}$$(v_{\mathrm{n}}$$\mathrm{n}$$\mathrm{n}$$\mathrm{s}_{\mathrm{n}}$$\mathrm{g}^{\mathrm{i}}(cu_{\mathrm{n}}, \mathrm{s}_{\mathrm{n}})$$\bullet$$\mathrm{n}$$\mathrm{g}_{\mathrm{n}}$3. 2 割引率と確率過程ゲームの種類
確率過程ゲームは繰り返しゲームの延長線上にあるものと考えられるから, 割引率をどのように考慮するかによって次のようなバリエーションがある.

219

.

割引ゲーム ;-.

,$\Gamma_{i}$各ステージの利得ベクトルに対して一$\text{期}$ごとに割引率$\lambda$を考慮$\mathrm{n}$ステージゲーム ;,時間 までの時間平均利得ベクトルを考慮$\Gamma_{J}$-$\mathrm{n}$割引なし (定常もしく平衡状態) ゲーム ;上記の ステージの平均利得ベクトル$\Gamma_{\varpi}$$\infty$-

3.3「$\mathrm{H}_{\dot{1}}\mathrm{s}\mathrm{t}0$$\mathrm{y}$$g_{\infty}= \lim_{narrow\infty}g_{n}$を考慮と戦略

ここで使う History は確率過程論における History と厳密には異なる。

確率過程論では状態の変化にのみ注目するがここではアクションという概念を導入されていることに注意すべきである. また, さらに注意を要する

Markov 決定過程論と深くかかのは 「戦略」 である。 確率過程ゲームは,わっている。「アクション」 と「戦略」 は非常に混同しやすいものである.

.
.

$\text{フ^{}\mathrm{O}}$

レイヤー i の History とは-状態とアクションの列

プレイヤー j の戦略とは-(,$\omega_{1^{\mathrm{i}}},$$\omega_{\mathrm{n}\cdot 1}:,$$\mathrm{s}\iota^{\mathrm{i}},$$,\ldots$.

-

く注意

$>$

$(\omega_{1^{\mathrm{i}}}, \mathrm{s}1^{\mathrm{i}}, ,\ldots , \omega_{\mathrm{n}\cdot 1}\mathrm{i}, \mathrm{s}_{\mathrm{n}^{\sim}1^{\mathrm{i}}},\omega_{\mathrm{n}^{i}})$:$\mathrm{s}_{\mathrm{n}\cdot 1},$$\rangle$$\omega_{\mathrm{n}^{\mathrm{i}}}$$arrow,9^{\cdot}$の推移確率ゲーム理論の 「混合戦略」 になっている !

Markov 戦略
History$\mathrm{b}_{\llcorner}^{\vee}\sigma \mathrm{k}$Markov 性は確率過程論では独立性を弱めた重要な概念である. 次にどのような状態移行するか考えるときにすべての History を意思決定者が考慮するとはアプリケーションを考える上からも考えにくい. 次の状態に移行するには現在の状態のみ依存するという考え方は理想的な単純化の一つである。 多重 Markov 性を考える応用もありうるがそれは時間と状態をとりなおして Markov と考えられることも多い.

220
3. 42 人ゼロ和ゲームでの例
以下のような 2 人ゼロ和ゲームを考える.

2 つの状態\Omega $=\{1, 2\}$の時右であるとする (利得行列の値の時は左,はプレイヤー 1 を示すものとする. )利得行列は$-110$.

$\omega=2$$\omega=1$$-110$$\ovalbox{\tt\small REJECT} 60$$06\ovalbox{\tt\small REJECT}$の時, (ここでは各行、 各列はアクションを示し、遷移確率 :行列要素の左が状態 1 へ、 右が状態 2 への遷移確率を示している)$\omega=1$$0)0.5)\ovalbox{\tt\small REJECT}$

状態遷移図を描くと以下の通り,とし, プレイヤー 2 を同様に移確率を示す.

$\mathrm{T},$$\mathrm{D}$$\mathrm{L},$$\mathrm{R}$

プレイヤー 1 の 2 つのアクションをとした. 状態今状態で遷移を, は遷

状態遷移図$\mathrm{p}$221
3. 5 例に対する割引ゲー の解法$\Delta$..
.

::の割引ゲーム値の割引ゲーム値
以下の 2 つの再帰式を計算 (ただし, val は行列の min-max 値, 割とする)
引率$\mathrm{v}$$\mathrm{u}$$\omega=1$$\omega=2$$\lambda=0.5$$v=val\{$0, $5*10+0.5(1*v+0*u)$$0.5*(-1)+(0.5*v+0.5*u)$$0_{1}5*(-1)05*v+\mathrm{O}.5\dot{*}u)0,5*10+0.5\dot{(}1\mathrm{A}_{1}v+0*u))$0,$u=val\{$ 0, $5*0+0.5*u$$5*3+0.5*u$$-u=0.5*u+0$ .Sval
これより$\mathrm{u}=2$同様にして$(\begin{array}{ll}0 66 0\end{array})=0.5u+1-$$\mathrm{v}=4$がわかる.

最適戦略は以下のようになることがわかる.
$\omega=1$$\omega=2$の時 :プレイヤー 1 (0. 5, 0. 5), プレイヤー 2(0. 5, 0.の時 :プレイヤー 1(1/3, 2/3), 列プレイヤー 2$5\rangle$$\langle 2/3, 1/3\rangle$

222

4. 木構造ネットワークへの確率過程ゲームの適用
4. 1

モデヲレ

ある階層の待ち行列が, 一階層下の 個の並列待ち行列に対して客を割り当てる状況を考える. Mohri(2005) と議論とほぼ同様の議論ができる.
$\mathrm{k}$個待ち行列の集合体
非協力ゲームとしてのプレイヤーは, ルータとのサーバの 2 プレイヤーとする. (待ち行列の集合体をまとめてプレイヤーと考えていることに注意する)
到着に関する考察は 2 章の結果を利用.
$\mathrm{k}$各待ち行列のバッファは無限大であると仮定する.
各待ち行列の処理方式は FCFS であるとする.
に対して指数サービス
下層の待ち行列のサービス率は各待ち行列$\mathrm{i}$とする (下付を行なうものとし, そのパラメータは
き添え字の 1 はプレイヤー 1 を示している), こ衷がプレイヤー 1 のアクションである.
プレイヤー 2 がどの待ち行列に客を割り当てるかというアクションをa2 で表現して, そのとる値は割り当てられる待ち行列の番号であると$\mathrm{a}\mathrm{l}(\mathrm{i})\in$$[\mu_{i},\overline{\mu}_{i}]$する.
プレイヤー 1 と 2 の間には非協力ゲーム状況があり, 各待ち行列のサービス率がルータには厳密には分からないとする. ここでは以下の情報が分かっていると仮定する.

一章時点の待ち行列の長さールータがどういつだ振り分け履歴があるかは分かっている

この問題をマルコフ決定過程として考えたい時に. 状態 : 各待ち行列の長さ、 直近のイベントの同定が必要になる. ここで注意したいのは, ルータが「客が到着時に意思決定する」 のに対して, サーバは 「いつでも意思決定する」 ことである. この状況を単純化するため, ルータに関して 「すべてのイベントで意思決定」可能と考えるとモデルを単純化できる. つまり,223

ルータが時間

1
時間$\mathrm{t}$$\mathrm{t}$でアクション$|$を取る

読替え

以降直近のイベントが到着なら客を待ち行列に振り分ける$|$. 状態 : 各待ち行列の長さ (だけでよい)
この状況で具\Phi 的に定式化を試みる.ということになる.

: 状態 s で queue への客が到着した直後の状態: 状態 s で queue への客が出発した直後の状態. p が真なら 1 、偽なら 0 を返す,
微小時間間隔 :状態の変化 (各 queue の長さの変化)$A_{i}(s)$$i$$D_{i}(s)$$i$$\Delta$$\pi\{p\}$$s=(s_{1},s_{2},\ldots,s_{k}.)arrow s^{\mathrm{I}}$

遷移率 (確率ではないことに注意) は以下のようになる$q_{\Delta}$(’$s$I$s,a_{1},a_{2}$)$\lambda\acute{p}_{i}\Delta+o(\Delta)$$(a_{2}=i,s^{1}=A_{i}(s),\mathrm{i}=1,2,\ldots,k)$$a_{1}(\mathrm{i})\Delta+o(\Delta)$$(s’=D_{i}(s),s_{i}\neq 0,i=1,2,\ldots,k)$$=$$p_{\dot{f}}-( \lambda^{t}p_{i}+\sum_{i=1}^{\mathrm{A}}.a_{1}(i)\pi\{s_{i}>0\})+o(\Delta)$$o(\Delta)$$(s’=s)$(otherwise)

このように議論を Mohri(2005) と同様に展開することができる.

4. 2

最適戦略について解析を進めると推移率、 利得関数とも
一プレイヤー 1 部分となっている$+$

プレイヤー 2 部分.. 有限計画期間の場合、 Markov
無限計画期間の場合、最適戦略が存在
定常戦略の存在

本稿での前提はて定常性の仮定をおいているために有限期間に対しては,

224
この定理が無限計画期間利得 (コスト) と最適政策 (戦略) を求めることはできない. これにはある意味での過渡解析が必要になる。 無限期聞にのみこの定理が有効である,

5.

まとめと今後の課題

本論では,木構造の待ち行列ネットワークに対する確率過程ゲームを用いた振り分けについて考察を行った. 定常性を最初から仮定している点は改善されるべき一番の点である. これには, 過渡解析が必要である. また,フィードバックを部分的に含んだ構造, 特に直列待ち行列にフィードバックの部分があるような場合について解析を行うことが今後の課題である.
[参考文醐
[11E. Altman. “A Markov game approach for optimal routing into aqueuin network”, 1994,Antipolis.
$\mathrm{g}$Technical Report 2178, INRIA Sophia. Filar and K. Vrieze,Processes”, 1996 Springer.

$[2]\mathrm{J}$“CompetitiveMarkovDecision. Hassin and M. Haviv, “To Queue or Not To Queue”, 2004, Kluwer
Academic Press.

$[3]\mathrm{R}$. Mertens, “StochasticGames”, Handbook of Game Theory
with Economic Application Vo1.3, 2002, Chapter 47, pp.1809-1832.

$[4]\mathrm{J}.\mathrm{F}$$[5]\mathrm{T}.\mathrm{E}.\mathrm{S}$. Raghavan and$\mathrm{J}.\mathrm{A}$. Filar, “Algorithms for Stochastic Games:of OR) , 1991,

ZOR( Mathematical Methods-A Survey”,$\mathrm{p}\mathrm{p}.437^{-}472$.

Shapley, “Stochastic Games”, Proceedings Nat. Acad. Of
Science USA, 1953, 39, pp.1095-1100.

$[6]\mathrm{L}.\mathrm{S}$$[7]\mathrm{S}.\mathrm{H}$. Tijs, T.E.S. Raghavan and$\mathrm{O}.\mathrm{J}$. Vrieze, “On Stochastic Games

with Additive Reward and Transition Structure”, Journal ofOptimization Theory and Applications, 1985, 47, pp.451-464.
. Vieille,
Stochastic Games: Recent Results”, Handbook ofGame Theory with Economic Application Vo1.3, 2002, Chapter 48,$[8]\mathrm{N}$“$\mathrm{p}\mathrm{p}.1833\cdot 1850$.

Mohri, “確率過程ゲームの計算機ネットワーク制御への応用”,
京都大学数理解 研 所 講究録 (to appear)$[9]\mathrm{H}.$$\ovalbox{\tt\small REJECT} H$$\Lambda\ovalbox{\tt\small REJECT}$