数理解析研究所講究録1093 巻 1999 年 15-2015方向通貨交換問題における予測を用いたアルゴリズム
米澤弘毅 (Kouki Yonezawa)*

岩間 –雄 (Kazuo Iwama)\dagger*

京都大学工学部情報学科\dag er 京都大学大学院庸報学研究科

1

はじめにオンライン金融問題における代表的戦略はいわゆる 「脅威原理」に基づくものである. これは, 何時如何なる時点で脅威的な事態が生じても–定の利得を確保することを保証する戦略で, 別の言葉で言えば, 最悪の場合の結果を最善にすることを目的にした保守的で安全な戦略であると言える. これは, オンラインアルゴリズムの性能評価が競合
比 (オフラインアルゴリズムの利得との比の最悪値) で計られることを考えれば自然なことではある. しかし, 実際的立場からは「面白み」に欠けるという指摘があることも確かである. この観点から, al-Binali は「ギャンブル性」の導入を提案した [2]. それは, 予測という概念の導入であり, 予測が当たればより良い結果が得られるが, 外れても脅威原理に基づく利得に比べて–定の減少のみに留まるというものである.

本稿で扱う金融問題は–方向通貨交換問題である. –方向通貨交換問題とは, ある–定の期間, レートが変動していく中で, ドルから円への交換が許されているという条件下において, できるだけ多くの円を得ることを目標とする問題である [1]. この問題には, レートの変動が断続的に為される連続型モデルと, 期日が与えられ その期日ごとにレートが–つだけ与えられるという離散型モデルがある.
El-Yaniv らは, それぞれのモデルに対して競合比が有界であるオンラインアルゴリズムを設計し, それが最適なオンラインアルゴリズムであることを証明している [1].

[2] では, 離散型モデルに対して予測を導入したオンラ
インアルゴリズムを発表した. 交換レートに関する予測が正しければ良い競合比が得ちれ, 予測が間違っていても, 従来のアルゴリズムより少しだけ悪い値に抑えられるというアルゴリズムがある [2]. しかし, ここでの議論は単純な 1
回だけの予測の場合のみを論じているに過ぎず, またより現実的と考えられる連続型モデルに対する議論もされていなかった.

本研究では, 連続型モデルに対し, この予測行動の–般化を試みる. つまり, 予測の種類について, [2] で論じられているレートがある値を越えるという予測 (本論文では
上予測と呼ぶ) の他に, レートがある値に達しないという下予測も許す. 更に 1 回だけの予測ではなく, ゲームが続いている限り 2 回 (以上) の予測も許す. これにより, 投資家の希望に応じて様々なパターンのアルゴリズムが設計できるようになった. 例えば, 予測が失敗しても, さらに新たな予測をすることによって, 従来のアルゴリズムでの結果を取り戻せる可能性があることもわかった. さらに,両方向通貨交換問題について, レートの変動にある制限を加えたモデルにおいて, 同様に予測を用いたアルゴリズムを設計し, それが–方向通貨交換アルゴリズムに対して設計したアルゴリズムと比較して良い結果をもたらすことが
わかった.

2

競合比

ある問題に対しては, 種々のオンラインアルゴリズムが構築されるが, その評価方法として オンラインアルゴリ

ズムとオフラインアルゴリズムの競合比 (Competitive Ra-というものがある. これは次のようなものである.
とし また, 問題にある問題に対し, 入力例を対するあるオンラインアルゴリズムを $A$ , 最適なオフライ
ンアルゴリズムを OPT とする. また,に対して $A$ の出力する解の利益を per, OPT の出力する解の利益をperfとすると, 競合比は,で定義される [2]. これが 1 に近い程, 良いオンラインアルゴリズ
ムであると言える.
$\mathrm{t}\mathrm{i}\mathrm{o})$$\Sigma$$\sigma$$\sigma$$f_{A}(\sigma)$$(\sigma)$3

3.1$r_{A}$$\sup_{\sigma\in\Sigma^{\frac{perf(\sigma)}{\mathrm{p}erf_{A}(\sigma)}}}$

通貨交換問題-方向通貨交換問題

最初は–定額のドルのみを持っていて, ある期間内で,連続的に変動していくレートの中で, ドルを円に交換することのみを許された条件下で 最終的にできるだけ多くの円を得ることを目標とする問題である.

3.2

限定型両方向通貨交換問題

一般の両方向通貨交換問題は, ある期間内で 連続して変動していくレートの中で, ドルと円の問の交換を許された条件下で, 最終的にできるだけ多くの円を得ることを目標とする問題である [1]. これに, レートの変動に関して制限を加える. その制限は, 次のようなものである.
「レートは初期値 $m$ から始まり, そこから単調に $M’$$(m<M’\leq M)$ まで増加し, 次の瞬間 $m$ に落ち, 以後,
レートはずっと $m$ のままである. 」
この条件下で できるだけ多くの円を得ることを目標とする問題 と定義する.

3.3

変数の定義

主な変数は以下の通りである.
$M$: レートの最大値$m$: レートの最小値. 簡単のため, レートの初期値は$m$ とする.
$D(x)$ : レート
で持っているドルの値.
初期値 $D(m)=1$ とする.
$Y(x)$ : レート
で持っている円の値.
初期値 $Y(m)=0$ とする.
$M$ または $m$ がわかっていないと, 定数の競合比は得られ
$x$

$x$

ないことがわかっている [1].

4

Threat-based algorithm

方向通貨交換問題問題に対する最適なアルゴリズムは,threal-based algo 加 lhm である [1]. これは, 次の規則によって取引をするものである. 但し, レートが のときに持っているドルの値を $D(x)$ , 円の値を $1^{i}(x)$ とする. また, 以下の議論では, $D(m)=1,$ $Y(m)=0$ とする.
$x$

規則 1 期間終了時には残っているドルをすべて円に交換する.

16(b) $md_{1}+y_{1}>N_{1}/r$ のとき

規則 2 規則 1 以外の場合は, それまでよりも高いレートでのみ取引する.
規則 3 規則 2 の条件で取引する場合, ドルが下のような値になるように取引を行う.
$x\in[m, r_{0}m]$$D(x)=1$$x\in(r_{0}m, M]$$D(x)=1- \frac{1}{r_{\mathrm{O}}}\ln$

このときは, 円をドルに交換することが許されていないため, レートがある値の条件は,まで待つことになる. 但し,$md_{1}+y_{1}=\tilde{N}_{1}/r$ である. その後は, レートに対し,$\tilde{N}_{1}(>N_{1})$$\tilde{N}_{1}$$\{$$x\in[\tilde{N}_{1}, N_{2}’]$$\frac{x-}{r_{0}m}$

このアルゴリズムの競合比は以下の式を満たす $r0$ である.

$D(x)$$=$$d_{1}- \frac{1}{r}\ln\frac{x-m}{\tilde{N}_{1}-m}$$Y(x)$$=$$y_{1}+ \frac{1}{r}(m\ln\frac{x-m}{\tilde{N}_{1}-m}*x-\tilde{N}_{1})$競合比がこれよりも良いオンラインアルゴリズムは存在しないことが示されている.
’(1)$r_{0}= \ln\frac{M-m}{r_{0}m-m}$

以下では, どのアルゴリズムでも規則 1 及び 2 に従って取引をする.

5

予測を用いたアルゴリズム

方向通貨交換問題の離散型モデルに対しては, 予測を用いたアルゴリズムが設計されている [2]. これは, 「レーまで上がるだろう $(m<l\mathrm{t}l_{1}\leq M)$ 」 と
トはある値
より小さい
いう予測を元に, 予測が当たれば競合比はものが得られ もし外れても, 我慢度 というパラメータを用いて, 競合比がか 0 になるようなアルゴリズムである.
ここでは, 予測の概念を連続型モデルに適用させる. 我々を2る, した. その 2 つとはは, レートに次のものである.
$M_{1}$$r_{0}$$t$.

$\bullet$$\text{関}g-$

レートは$M_{1}$$\text{予^{}\backslash }\mathbb{R}^{1}$$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT} \mathrm{f}\mathrm{f}\mathrm{l}^{\Rightarrow}$

を超えることがあるだろう

レートはずっと未満だろう
前者を上予測, 後者を下予測と呼ぶことにする. この予測を用いてアルゴリズムを設計する前に, 設計を簡単にする
ための定理の証明を行う. 但し以下では, $m$ 及び $M$ は与えられているものとし, これによって $r0$ はわかっているものとする.
定理 レートの区間 $[N_{1}, N_{2}]$ 内で, アルゴリズム $A$ が$D(N_{1})=d_{1)}Y(N_{1})=y_{1}$ を満たすとする. このとき, 取引できる間は競合比 を得られる最適なアルゴリズム $A$ は意に決定できる.
$M_{1}$

$r$

証明

となる

51

上予測を採用する場合「レートはを超えることがあるだろう」 という予測を用いたアルゴリズムを設計する. これは, レートがを超えれば,
より良い競合比噂が得られ, もし超えな
くても, 競合比はか 0 までで抑えられるというものである.
但し, $M_{1}>$ 加 o $m$ とする.
1. レートが $[m, M_{1}]$ の間は, 開始時のドルと円, 競合比がわかっているから, 定理より競合比 tr。を得られるアルゴリズムが設計可能である. この区間のレートで持っているドル及び円の値を $D_{1}(x),$ $Y_{1}(x)$ とすると,$M_{1}$$M_{1}$$r_{0}$$tr_{0}$$x$$D_{1}(x)$$Y_{1}(x)$れるアルゴリズムが設計できる. この区間のレートで持っているドル及び円の値を $D_{2}(x),$ $Y_{2}(x)$ とすると,$x$$D_{2}(x)$$=$$d- \frac{1}{r_{1}^{\star}}\ln\frac{x-m}{M_{1}-m}$$Y_{2}(x)$$=$$y+ \frac{1}{r_{1}^{\star}}(m\ln\frac{x-m}{M_{1}-m}+x-M_{1})$でなければ, threat-based strategy と同様にして, レート $x\in[rm, N_{2}’]$ に対し,?.

$Y(x)$In$\underline{x-m}$となる. 但し, 及び はレートで競合比姪を満たすような定数である. この 2 つは後で求める.
以下, $D_{i}(x),$ $Y_{i}(x)$ は同様の意味で用いる. $d,$ については, 以下の条件が存在する.
$d$$7^{\cdot}m-7n$$\frac{1}{r}(m\ln\frac{x-m}{rrn-m}+x-rm)$$=$が成り立つ. 但し,まで取引できれぱ $N_{2}’=$まで取引できなければ $N_{2}’<$であり, もしとなる.
$N_{2}$$M_{1}$$y$$y$$N_{2}$$N_{2}$$\frac{1}{tr_{0}}(m\ln\frac{x-m}{tr_{0}m-m}+x-tr_{0}m)$

$=$

となる.

このとき, $D(N_{1})=1,$ $Y(N_{1})=0$ である. も$=$$tr_{0}m-m$

2. レートが $[M_{1}, M]$ の間は, 定理より競合比較を得ら

し $N_{2}\leq rm$ ならば, $A$ は全く取引しない. そう$D(x)$$1-\ln\underline{1}\underline{x-m}$$=$$tr_{0}$

1. $N_{1}\leq rm$ のとき$1-\underline{1}$口

以下, それぞれの予測を用いてアルゴリズムの設計を行う. 1 段階の場合は, どちらも 2 つのアルゴリズムをつなぎ合わせたものになる.

$D_{1}(M_{1})-d$$=$$md+y$$=$$\frac{1}{M_{1}}(y-Y_{1}(M_{1}))$$N_{2}$

2. $N_{1}>rm$ のとき

この場合は, 次の 2 つの場合に分けられる.
(a) $md_{1}+y_{1}\leq N_{1}/r$ のときである量のドルを円
このときは, レートに交換する. つまり, 交換した後のドル及び円をとすると, $md_{1}’+y_{1}’=N_{1}/r$となるように交換する. その後は, レートに対して$N_{1}$$d_{1}’,$

この条件から,$\frac{M_{1}}{r_{1}^{\star}}$$d=D_{1}(M_{1})- \frac{M}{M_{1}-}\overline{m}(\frac{1}{r_{1}^{\star}}$$=$$d_{1}’- \frac{1}{r}\ln\frac{x-m}{N_{1}-m}$$Y(x)$$=$$y_{1}’+ \frac{1}{r}(m\ln\frac{x-m}{N_{1}-n\mathrm{z}}+x-N_{1})$

,

と求められ

は,
このような条件を満たす礎は–意に定まる.
$D_{2}(M)=0$ としたときの解であるから, 畦は次の方程式
る$r_{1}^{\star}$の解$D(x)$$\frac{1}{tr_{0}})(=D_{2}(M_{1}))$$y=Y_{1}(M_{1})+ \frac{M^{2}}{M_{1}-}\overline{m}(\frac{1}{r_{1}^{\star}}-\frac{1}{t_{\mathrm{f}0}})(=Y_{2}(M_{1}))$$y_{1}’$$x\in[N_{1}, N’\underline,]$一$r_{1}$である.

$1- \frac{1}{tr_{0}}\ln\frac{M_{1}-m}{tr_{0}m-m}-\frac{M_{1}}{M_{1}-m}(\frac{1}{r_{1}}-\frac{1}{tr_{0}})-\frac{1}{r_{1}}\ln\frac{M-m}{M_{1}-m}=0$となる.

これを解くと,$r_{1}^{\star}$は次のように表せる.

17を固定して考える. $m=100,$ $M=200,$ $t=1.01$ としを 120 及び 150 に固定したときのと湾との関係を図 2 に示す. この結果も, 図 1 と同じくごく自然な結果$M_{1}$て,$r_{1}^{\star}= \frac{lVI_{1}-m}{(M_{1}-m)(1-\frac{1}{tr_{\mathrm{O}}}\ln\frac{M}{tr_{0}}\mathrm{L}m^{\frac{-m}{-m,})+^{\mathrm{J}I}}tr_{0}arrow J}\cross$$( \frac{M_{1}}{M_{1}-n\mathrm{z}}+\ln\frac{M-m}{M_{1}-m})$(2)$M_{1}$$M_{2}$

である差言交 乙$-$ちなみに, レート $x\in[m, M_{1}]$ では, $mD_{1}(x)+Y_{1}(x)\leq$が, レート $x\in[M_{1}, M]$ では, $mD_{2}(x)+Y_{2}(x)= \frac{x}{r_{1}^{\star}}$$\underline{x}$$tr_{0}$が成り立っている.
$m=100,$ $M=200,t=1.01$ のときのと噂の関係を図 1 に示す. なお, このとき $r_{0}\approx 1.28$ である.
$M_{1}$

S.3[才測 t 殊用す \Phi 陽省「レートはずっと未満だろう」 という予測を用いた
アルゴリズムを設計する. つまり, レートがずっと未$M_{1}$$M_{1}$

を超満ならば、競合比礎を得ることができ, レートがえることがあっても, 競合比はか 0 で抑えることができる$M_{1}$

ものである.

レートによって以下の 2 つの区間が考えられる. 以下その解析を行う.
レートが52

二段階上予測り, 2 回目の予測が当たればさらに良い競合比が得られる
ようなアルゴリズムを設計する. 但し, 1 回目の予測が当たり, 2 回目が外れたときは, 競合比はである.
$tr_{1}^{\star}$ム$\text{を}$つ$k\mathrm{E}^{P\bigwedge_{\Pi}}$下の 3 つの用いたアルゴリズムは, 3 つのアルゴリズ

i\supset せたものと考えられる. レートによって以えられる. 以下その解析を行う.

$\text{区}\mathrm{e}\mathrm{B}5\mathrm{B}\vec{>}\text{考}$レートが $[m, M_{1}]$ の間は競合比か 0 を得るアルゴリズムを設計する. 定理.k り,.

$1- \frac{1}{r_{1}^{\star}}\ln$

レートが $M_{1}$ になった後, さらに上予測をすることによ$-\mathrm{g}-\mathfrak{p}\mathrm{g}\text{予^{}\backslash }\mathrm{f}\mathrm{f}\mathrm{l}^{1}\text{を}$$\mathrm{A}r\tau_{1}$$\lfloor m,$] の間は競合比咬を得るアルゴリズムを設計する. 開始時のドルと円, 競合比礎がわかっているので, 定理よりレート $x\in[r_{1}^{\star}m, M_{1}]$ では, $D_{1}(x)=$である.

レート $x\in[tr_{0}m, M_{1}]$ に対して,$D_{1}(x)=1- \frac{1}{tr_{0}}\ln\frac{x-m}{tr_{0}m-m}$$\frac{x-}{r_{1}^{\star}m}$

レートが $[M_{1}, M]$ の間は競合比 $tr0$ を得るアルゴリズムを設計する. $mD_{1}(M_{1})+Y_{1}(M_{1})=M_{1}/r_{1}^{\star}>M_{1}/r$であるから, 定理より, $mD_{1}(M_{1})+Y_{1}(M_{1})=\overline{M}_{1}/tr_{0}$まで待たなければならない. 上式よりを満たすようなと求められる. すると, $D_{2}(x),$ $Y_{2}(x)$ は次のように書ける.
$\overline{M}_{1}$$M_{1}= \frac{t}{r}\gamma\Delta M_{1}\star 1$$D_{2}(x)$$=$$D_{1}(M_{1})- \frac{1}{tr_{0}}\ln\frac{x-m}{\overline{M}_{1}-m}$$Y_{2}(x)$$=$$Y_{1}(M_{1})+ \frac{1}{tr_{0}}(m\ln\frac{x-m}{\overline{M}_{1}-m}+x-\overline{M}_{1})$である.

レートが $[M_{1}, M_{2}]$ の間は競合比堵を得るアルゴリズ

ムを設計する. レート
及びレートでのドル及び円 $(D_{2}(M_{1}), Y_{2}(M_{1})$ は, 前の区間でのアルゴリズムのド
ル及び円の値 (ここでは, $D_{1}(M_{1}),$ $Y_{1}(M_{1})$ ), 競合比醗から求められる. よって, レートに対して,$D_{2}(x)=D_{2}(M_{1})- \frac{1}{t\prime_{1}^{\star}}\ln$である. 但し, 咬は式$M_{1}$$M_{2}$$x\in[M_{1,\mathit{1}}\mathrm{W}_{2}]$$\frac{x-}{M_{1}}$(2) を満たす.
レートが $[M_{2}, M]$ の間は競合比袴を得るアルゴリズム

但し,でなければならないので,の取り得る値は, $m<M_{1}\leq tr_{0}r^{\star}" M$ となる. レート $x\in[m, M_{1}]$ では $mD_{1}(x)+Y_{1}(x)\leq\underline{x}$ が成り立ち, レート $x\in[M_{1}, M]$
では, $mD_{2}(x)+Y_{2}(x) \leq\frac{x}{tr_{0}}$ が成り立つ.
は次の方程式を満たす である.
$\overline{M}_{1}\leq M$$r_{1}^{\star}$$r_{1}^{\star}$を設計する. この区間のレート で持つべきドルの値を$D_{3}(x)$ とすると, $D_{3}(x)=D_{3}(M_{2})- \frac{1}{r_{2}^{\star}}\ln$
であ$x$$r_{1}$$1-\ln-\ln-=0\underline{1}\underline{M_{1}-m}\underline{1}\underline{M-m}$$\frac{x-}{M_{2}}$る.

$M_{1}$$r_{1}$$r_{1}$rn–m$tr_{0}$(3)$M_{1}-m$$m=100,$ $M=200,t=1.01$ のときのと燦の関係を図 3 に示す.
この図を見ると,が 140 から 150 のところでは,はそんなに変わらないが 180 のところと比べてみても,のに予測が当たる確率には大きな違いがある. よって,
$M_{1}$

3 番目の事実より, 段階上予測によるアルゴリズムも,最初と最後の区間のアルゴリズムと, その区間で得たい競合比を決めれば区間毎のアルゴリズムが決まるので, 全体のアルゴリズムも決定できる.
$n$$D_{2}(M_{1})$及び $D_{3}(M_{2})$ の値は次のようになる.

$D_{2}(M_{1})$$=$$D_{1}(NI_{1})- \frac{M_{1}}{t(M_{1}-m)}(\frac{1}{r_{1}^{\star}}-\frac{1}{r_{0}})$$D_{3}(M_{2})$$=$$D_{2}(M_{2})- \frac{M_{2}}{M_{2}-m}(\frac{1}{r_{2}^{\star}}-\frac{1}{tr_{1}^{\star}})$$M_{1}$$M_{1}$$l_{1}^{\star}$$M_{1}$を 140\sim 150 に取ることは得策ではないと言える.

5.4

二段階下予測上予測では, 予測が外れたかどうかは期間が終わらなけ

ればわからない. これに対して下予測では, 予測が外れた
ことはレートがになった時点でわかる. そこで, 今度$M_{1}$

18

図 4:$iV\mathit{1}1X$

固疋したどさの$\mathit{1}V\mathit{1}2$と$r_{2}\nu y$

[

係

になり 予
して, レーは,ffil i‘’p ト*\iota k ことがわかったら そこでもう –度下予測をしたれば, 従来のアルゴリズムでの競合比て, その#\theta ‘
ことを考える.
を取$\text{下予}\mathrm{R}^{1}\ovalbox{\tt\small REJECT} \text{丞ついて取引}\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}\supset$$\mathit{1}V\mathit{1}1$$\mathrm{I}\mathrm{J}p\mathrm{i}\text{当}$$\text{り}\ovalbox{\tt\small REJECT}- t$$r_{0}$\emptyset ip ト h た場合, 次に「レートはずっと
1 回目
に従ってアルゴリズムを設計する.
未満だろう」 といたれば競合比確が得られ,
これは, もし 1 回目の\neq R|l
1 回目の予測が外れても, 2 回目の予測が当たれば競合比が得られ, もし 2 回目も外れてしまったら競合比 $r_{2}(>$を得るように取引するものである.
レートによって以下の 3 つの区間が考えられる. 以下そ$M_{2}$$\text{の予^{}\backslash }ffl1$$\text{う予^{}\backslash }ffl\mathrm{I}$$>\text{当}$$r_{0}$$r\mathrm{o})$.

れぞれの区間でアルゴリズムを設計する.
レートが $[m, M_{1}]$ の問は, 競合比噂を得るアルゴリズ
ムを設計する. 定理より, レート $x\in[r_{1}^{\star}m, M_{1}]$ の時には式 (3) を満た
となる.
は,

.

$D_{1}(x)=1- \frac{1}{r_{1}^{\star}}\ln$$r_{1}^{\star}$$\frac{x-}{\mathrm{r}_{1}m}$

す.

レートが $[M_{1}, M_{2}]$ の間は, 競合比ムを設計する. レート同様であるが,$M_{1}$

を得るアルゴリズ
までは取引しないのは–段階とである. これより, レート$r_{0}$$\overline{M}_{1}=\frac{r}{r}\mathrm{A}M\star 11$$x\in[\overline{M}_{1}, M_{2}]$.

では $D_{2}(x)=D_{1}(M_{1})- \frac{1}{r_{0}}\ln$$\frac{x-}{M_{1}}$とにするのはあまり好ましくない. この条件では, 以下のような性質がある.
を 120 やそれ以下に設定すると, 較は良いが1.
の条件は厳しくなる.
を 140 近辺に設定すると, 1 回目の予測に失敗し2.
てもを得る確率は高くなるが, 較の結果はあまり良くない.
を $M$ の近くに設定すると, 予測が当たる確率は3.
高くなるが, 得られる噂は悪くなるし, 失敗した後を得るようなアルゴリズムは設計できない.
$M_{2}$$M_{1}$$M_{1}$

なる.

$r_{0}$

レートが $[M_{2}, M]$ の問は,を得るアルゴリズ
は,である. 但し, $M_{2}=$競合比
ムを設計する. 先程と同様に, レート$D_{3}(x)=$.

$. \frac{\prime r}{r}\mathrm{z}_{M_{2}}\mathrm{o}$$D_{2}(M_{2})- \frac{1}{r_{2}}$石$r_{2}$$\frac{x-}{M_{2}}$$x\in[\overline{M_{l}\prime},$$M\underline{]\text{で}}$である.

$r_{0}$

が得られるのは, $D_{3}(M)=0$ のときであるから,は次の式を満たす.
$r_{2}$$r_{2}$$1- \frac{1}{r_{1}^{\star}}\ln\frac{M_{1}-m}{r_{1}^{\star}m-m}-\frac{1}{r_{0}}\ln\frac{M_{2}-m}{\overline{M}_{1}-m}-\frac{1}{r_{2}}\ln\frac{M-m}{\overline{M}_{2}-m}=0$との関係について調を固定したときのまず,$m=100,$ $M=200,t=1.01,$ $r_{0}\approx 1.28,$ $M_{1}=$$M_{2}$$M_{1}$

べる.
$120$

と
としたときのである.
$M_{2}$

き,H4 から)$r_{2}$$r_{2}$の関係を図 4 に示す.

このと$r_{1}^{\star}\approx 1.17$ととの関係はほぼ線型とみなしてよい.
に取ってみても同様であった. これも, ごく$M_{2}$$r_{2}$$M_{1}k\mathrm{f}\mathrm{f}\mathrm{i}\text{の}\mathrm{f}\mathrm{f}\mathrm{L}$

自然 k

6

限定型両方向通貨交換問題

6.1

従来のアルゴリズム

一般の両方向通貨交換問題に対する従来のアルゴリズム
は, レートが増加している区間では以下の規則に従って取引する [1].
規則 1 レートが $[m, r_{0}m]$ の間は取引しない.
規則 2 レートが $(r_{0}m, M]$ の間は, ドルの値が次のようになるように取引する.

\check c ある.

との関係について調を固定したときのの値をどれほどに設定するかは問題ではあるが,とした.
2 回失敗しているという意味で,$m=100,$ $M=200,$ $t=1.01,$ $r_{0}\approx 1.28,$ $r_{2}=t^{2}r_{0}$ ととしたときのの関係を図 5 に表す.
はの増加に従って,図 5 よりこの条件下では,$M_{1}$$\mathrm{s}_{\theta?\mathrm{Y}\subset,r_{2}}$べる.

$M_{1}$$D(x)=1- \frac{1}{r_{0}}\ln\frac{x-m}{r_{0}m-m}$$M_{2}$$r_{2}$$r_{9,\sim}=t^{2}r_{0}$$M_{1}$$M_{2}$$M_{2}$$M_{1}$

指数的に増加していくことがわかる. そして, 予測が失敗したときにを取り戻す確率を上げたければ, レートを140 付近にするのが得策であると思われる. しかし, 図 3 をを 140 付近の立場からだと,見るとわかるように,$r_{0}$$r_{1}^{\star}$$M_{1}$

レートが減少する区間に入ったら, 残っているドルをす
べて円に交換し, 次の取引を設計する.
は式 (1) を満たす. 限定型両方向通貨交換問題で考えであることがわかる.
てみると, 明らかに競合比は$r_{0}$$r_{0}$

6.2

上予測を用いたアルゴリズム

上予測を用いたアルゴリズムは, –方向通貨交換問題に対するアルゴリズムと何ら変わらない. よって, 得られる競合比も同じである.

19

6.3

下予測を用いたアルゴリズム

下予測を用いたアルゴリズムは, -方向通貨交換問題に対するアルゴリズムとは少々異なる. レートによって 2の区間に分けられるので, 以下それぞれについて解析する.
$\cdot\supset$

レートが $[m, M_{1}]$ の間は,ムを設計する.

定理より,$D_{1}(x)=1- \frac{1}{r_{1}^{\star}}\ln$$\frac{x-}{r_{1}^{\star}m}$

競合比咬を得るアルゴリズ$\text{レ}-$$\text{ト}x\in[tr_{0}m, M_{1}]$

では,

である.

レートが $[M_{1}, M]$ の間は, 競合比 tr。を得るアルゴリズ

ムを設計する. ここで, 今回は円をドルに交換することが許されているので, レート
で円をドルに交換し, 交換
した後の :j 及び円を $d,$ としたときに, $md+y=M_{1}/tr_{0}$となるようにすればよい. $d-D_{1}(M_{1})= \frac{1}{M_{1}}(Y_{1}(M_{1})-y)$$M_{1}$$\mathrm{t}$

$y$

より,

$d=D_{1}(M_{1})+ \frac{M}{M_{1}}\overline{-m}(\frac{1}{r_{1}^{\star}}-\frac{1}{tr_{0}})(=D_{2}(M_{1}))$,と $D_{1}(M_{1})$ から,と求められる. よって, レート $x\in[M_{1},$では, $D_{2}(x)=$となる. ・レートが $[M_{2}, M]$ の間
は, 競合比 $r_{2}(r_{2}>r_{0})$ を得るアルゴリズムを設計する.
$M_{2}|$$D_{2}(M_{1})- \frac{1}{r_{0}}\ln$

である.

よって,

$\frac{x-}{M_{1}}$上と同様にして, $D_{3}(M_{2})=D_{2}(M_{2})+M_{2}-m arrow M(\frac{1}{r0}-\frac{1}{r_{2}})$となるから, レート $x\in[M_{2}, M]$ では, $D_{3}(x)=D_{3}(M_{2})-$$\frac{1}{r_{2}}\ln$$\frac{x-}{M_{2}}$である. .

し,の取り方には注意が必要である.
すべき条件は次の通り.
$\llcorner \mathrm{B}$1.
2.

$M_{2}$$M_{2}$が満た$M_{1}<M_{2}<M$$D_{2}(M_{2})\geq\overline{0}$$m=100,$ $M=200,i=1.01,$ $r0\approx 1.28,$ $r_{2}=t^{2}r0$ ととしたときの,との関係を図 7 に示す.
$M_{1}$$y=Y_{1}(M_{1})- \frac{M^{2}}{M_{1}-}\overline{m}(\frac{1}{r_{1}^{\star}}-\frac{1}{tr_{\mathrm{O}}})$$D_{2}(lVI_{1})=D_{1}(M_{1})+ \frac{M}{M_{1}}\overline{-m}(\frac{1}{r_{1}^{\star}}-\frac{1}{r_{0}})$$M_{2}$

レート $x\in[M_{1}, M]$ では,$D_{2}(x)$$=$$D_{2}(M_{1})- \frac{1}{tr_{0}}\ln\frac{x-m}{M_{1}-m}$$Y_{2}(x)$$=$$Y_{\theta}( \sim M_{1})+\frac{1}{tr_{0}}(m\ln\frac{x-m}{M_{1}-m}+x-\mathrm{J}\mathcal{V}I_{1})$$r_{1}^{\star}$

は次の方程式を満たす解$r_{1}$である.

$1- \frac{1}{r_{1}}\ln\frac{lVI_{1}-m}{r_{1}m-m}+\frac{\Lambda l_{1}}{M_{1}-m}(\frac{1}{r_{1}}-\frac{1}{tr_{0}})$$- \frac{1}{tr_{0}}\ln\frac{M-m}{M_{1}-m}=0$

ここで,の取り方には注意しなければならない.
の満たすべき条件は次の通り.
1. $m<M_{1}<M$$M_{1}$

2.

(4)$M_{1}$$D_{1}(M_{1})\overline{\geq}0$$m=100,$ $M=200,t=1.01,$ $r_{0}\approx 1.28$ における,$M_{1}$と梵との関係を図 6 に示す.

$\mathrm{o}.0$—JUJ $I$ ノレ$\overline{\lrcorner}/1\wedge \mathit{4}Uj\overline{\mathrm{H}}$7テ

前述した 2 つのアルゴリズムの考え方を合わせたアルゴ
リズムを設計することもできる. –段階の場合は, 次の 2
つの区間に分けられるので 以下それぞれについて解析を行う. 但し, $R_{1}\in[0,1]$ であり, $R=0$ ならば両方向のア\iota , ゴリズムと –致し, $R=1$ ならば–方向のアルゴリズムと –致する.
レートが $[m, M_{1}]$ の問は, 競合比姪を得るようなテルゴリズムを設計する. 定理より, レート $x\in[r_{1}^{\star}m, M_{1}]$ では,である.
$D_{1}(M_{1})=1- \frac{1}{r}\mathrm{r}\ln\frac{x-}{r_{1}mm}1\text{ }$レートが $[M_{1)}M]$ の間は, 競合比オァ0 を得るようなアルゴリズムを設計する. ここで,からすぐに取引を再開するのではなく,で調整した後から取引を再開するようにする. すると, レート $x\in[\overline{M}_{1}, M]$ では$M_{1}$$\overline{M}_{1}(>M_{1})$$M_{1}$$D_{2}(x)=D_{2}( \overline{M}_{1})-\frac{1}{tr_{0}}\ln$畦は次の方程式を満たす
二段階ト予測方向と同様に 一回予測が間違っていても, 2 回目のとなるようなアルゴ)1 ズムを設
予測が当たれば競合比計する. レートによって 3 つの区間に分けられるので, 以下それぞれについて解析する.
レートが $[m, M_{1}]$ の問は, 競合比噂を得るアルゴリズ
ムを設計する. $D_{1}(x)$ は–方向のときと全く同様である.
は式 (4) を満たす.
レートが $[M_{1}, M_{2}]$ の問は, 競合比を得るアルゴリズ
ムを設計する. レート
で持っているドルは, 競合比 $r0$である. ここで,$\overline{M}_{1}=$である.

$M_{1}+R_{1}(_{f}tr_{1}arrow M_{1}-M_{1})$6.4$\frac{x-}{M_{1}}$$r_{1}$である.

$1- \frac{1}{r_{1}}\ln\frac{M_{1}-m}{r_{1}m-m}+\frac{1}{M_{1}-m}(\frac{M_{1}}{r_{1}}-\frac{\overline{M}_{1}}{tr_{0}})$$r_{0}$$r_{1}^{\star}$$r_{0}$$M_{1}$$- \frac{1}{tr_{0}}\ln\frac{M-m}{\overline{M}_{2}-m}=0$(5)$m=100,$ $M=200,t=1.01,$ $r_{0}\approx 1.28$ としたときの,と畦との関係を,の値を付して図 8 に示す.
次に二段階下予測について考える. レートによって 3 区$M_{1}$$R_{1}$

そるれそれについて解析を行う.

$\text{間に}.\text{分けられ_{}2}\text{るの}\tau\cdot \text{以下}TR_{1},\in[0, 1]\text{あ}$

こ

20

参考文献
, and G.Turpin. ‘(Com[1] R.El-Yaniv, A.Fiat,
petitive Analysis of Financial Games’), Proc. 33th
IEEE Symposium on Foundations of Computer Science (FOCS), pp.327-333, 1992.
$\mathrm{R}_{:}\mathrm{K}\mathrm{a}\mathrm{r}\mathrm{p}$[2] Sabah -Binali. “The Competitive Analysis of Risk
Taking with Applications to Online Trading , Proc.
38th IEEE Symposium on Foundations of Computer.
Science (FOCS), pp.336-344, 1997.
$\mathrm{a}1$

[

.

.

レートが

ムを設計する.

$r_{1}^{\star}$

レートが $[M_{1}, M_{2}]$ の問は, 競合比 $r0$ を得るアルゴリズ

ムを設計する.

.

の間は, 競合比梵を得るアルゴリズ
は式 (5) を満たす.

$[m, M_{1}]$

レート $x\in[\overline{M}_{1}, M_{2}]$ のときは, $D_{2}(x)=$$D_{2}( \overline{\mathit{1}\mathrm{W}}_{1})-\frac{1}{r_{0}}\ln$$\frac{x-}{M_{1}}$である.

レートが $[M_{2}, M]$ の間は, 競合比

ルゴリズムを設計する.
$D_{3}(x)=D_{3}( \overline{M}_{2})-\frac{1}{r_{\lrcorner’}}$$r_{2}(\underline{r_{2}}<r_{0})$を得るア

レート $x\in[M_{2}, M]$ のときは,石$\frac{x-}{\hat{M}_{2}}$である.

ここで, $\overline{M}_{1}=M_{1}+R_{1}(_{1}\frac{r}{r}\star 1M_{1}-M_{1}),\overline{hI}_{2}=M_{2}+$$R_{2}(_{0} \frac{r}{r}1M_{arrow},-M\underline{o})$である.

$m=100,$ $M=200,t=1.01$ として, $R_{1}=R_{2}=$との関係を, $R$ のに固定したときの値を付して図 9 に示す.
$R,$ $r_{2}=t^{2}r_{0}$$M_{1}$$M_{2}$

図 8 よ ), –力回と岡力 |mj jL 刈] @1 ノ$|$$r_{1}^{\star}$」$-,/\mathrm{A}rightarrow$によるの値の中間を取るようなアルゴリズムが設計可能であることがわかる. 当然, そのとき

$r_{0}$を取り返すときの$M_{2}$の設定の ff 方 \S ), 両者の問となることが, 図 9 でわかる. たの値には影響しないようである.
の値は,だ,$R_{2}$

7$M_{2}$

おわりに

今回は 通貨交換問題に対するアルゴリズムに, 予測とこの問題では, 取引の際にかかる手数料などは考えていないが, そういった問題も存在する [4]. 今まで述べてきたアルゴリズ
ムの設計の方法が 他の問題のモデルに対しても活かせるのかどうか, 興味深いところである. さらに, 一般的な両方いう概念を入れることによる改良を試みた.

向通貨交換問題に対して, アルゴリズムの改良が行われているが [4], 予測を用いるという考え方でさらに改良ができないか, というのも非常に興味深い.

$3_{\rfloor}^{1}$

Richard M. Karp. “On-Line Algorithms Versus OffLine Algorithm : How Much is it Worth to Know
the Future?”, Proc. IFIP 12th World Computer Congress, Vol.1, pp.416-429, 1992.

[4] 檀浦詠介, 櫻井幸–. “取引手数料を考慮したオンライ
ン為替交換アルゴリズム”, 情報処理学会論文誌 Vo1.39,
No. 1, pp.1-10, 1998.