時間序列搜索問題的在線決策算法

張瑞英,張遠平

(蘭州理工大學計算機與通信學院，中國 蘭州 730050)

隨著在線算法的深入研究，在線決策問題已經成為一個熱點研究問題．在線決策問題是研究不完全信息下的決策問題，即輸入總是逐步被提供，對于每個輸入部分，在線算法需要在不知道以后信息的情況下給出輸出．由于不可能知道和預測未來的確切信息，因此往往無法對問題做出最優決策，而只能盡量給出問題的滿意決策．而本文研究的時間序列搜索問題是現實中一個典型的在線決策問題，決策算法性能由競爭比決定，即決策結果與離線最優決策結果的某一比值[1-2]．

最初的時間序列搜索模型是由El-Yaniv等建立的[3]．El-Yaniv等研究了已知價格在區間[m，M]波動的時間周期為n的時間序列搜索問題，提出了保留價格的確定性算法和基于風險的隨機性算法，并分析證明了算法的競爭比[4]．1999年Al-Binali在此基礎上對該問題做了進一步研究，依據在線者對未來的預期和所能承受的風險來確定出一個在線策略集合，而后根據預期成功后最小的約束競爭比來選擇在此模型下的最優在線策略[5]．Lorenz等研究了k最大序列搜索問題和k最小序列搜索問題，提出了相應的確定性算法和隨機性算法，并運用最壞情況分析計算了算法的競爭比[6]．Damaschke等研究了價格上下界限隨著時間以一種特定方式變化的時間序列搜索問題，提出了最優確定性算法和近似最優隨機性算法[7]．Xu等通過引入利潤函數對最初的時間序列搜索模型進行了擴展，然后運用最大最小定理提出了已知時間周期的確定性算法(Algorithm with Known Duration，簡寫為AKD)[8]．

與時間序列搜索問題緊密相關聯的問題是單向交易問題，El-Yaniv等在文獻[4]中指出任意的確定性單向交易算法都可以看作隨機性時間序列搜索算法．2009年，Fujiwara等對單向交易問題進行了平均情況競爭比分析，基于最大匯率服從一個已知分布的假設，采取不同的最優化標準得出了相應的最優化策略[9]．2004年，Kakade等在單向交易模型基礎上引入了量的概念，研究了量權平均價格交易和受限訂單交易[10]．

本文是在Xu研究的模型[8]基礎上提出了隨機性決策算法RAKD(Random Algorithm with Known Duration)，并分析證明了其競爭比，最后通過實驗與確定性算法進行了算法性能比較，分析及實驗結果表明該算法可以在一定情況下降低算法競爭比．另外El-Yaniv等人研究的時間序列搜索問題模型[4]因為沒有引入利潤函數，因此應用具有一定的局限性，而與其相比，本文研究的時間序列搜索算法應用范圍較為廣泛．

1 基本模型及概念

基本模型：一個在線者在一個報價序列中選擇且只能選擇一個價格，目的是在兌換貨幣1為貨幣2時最大化地獲得利潤．給定n個不相交的時間段，每個時間段稱為一個時間周期．在第i(i=1,2,…，n)個時間周期，在線者獲得一個報價pi，然后必須立刻決定是否要在這個時間周期接受該價格，一旦在線者接受了價格pi，則交易結束，在線者獲得的利潤為fi(pi)，即第i時間周期接受價格pi的利潤．否則pi無效，pi+1在下一個時間周期到達．

對于本文研究的在線時間序列搜索問題，有以下3個基本假設

(1) 價格在區間[m，M]，在線者預先知道n，m,M的值以及利潤函數f的表達式．

(2) 利潤函數f是連續的且是價格p的遞增函數．

(3) 對于任意的匯率p∈[m，M]，f1(p)≥f2(p)≥…≥fn(p) ．

在假設(1)中，如果n=1，則在線和離線情況下，在線者只能接受唯一的一個價格，因此在線和離線情況下，在線者會獲得同樣的利潤，所以在后面的分析中我們只考慮n≥2的情況．假設(2)和(3)說明在每一個時間周期，較大的價格對應大的利潤，對于每一個價格，早期接受獲得的利潤高于在后期接受獲得的的利潤．并且注意到在上述模型中如果fi+1(M)≤fi(m)在某一時間周期i成立，則在線者肯定會在時間周期i或i之前接受一個價格并結束交易，這是因為對于任意kfk(m)>fi(m)可知在線者在時間周期i或之前可以獲得較高利潤，所以在后面的分析中我們只需要考慮fi+1(M)>fi(m)的情況．

另外為了后面敘述清晰，先定義如下符號：

pi——第i個時間周期的價格，

fi(pi)——第i個時間周期對于給定的價格pi所獲得的利潤，

Si——第i個時間周期交易的貨幣1的數目，

Di——第i個時間周期交易后，在線者仍擁有的貨幣1的數目.由定義可知：Di=Di-1-Si，并定義D0=1表示在未進行交易時在線交易者擁有的貨幣1的初始值為1．

Yi——第i個時間周期交易后，在線者擁有的貨幣2的數目,由定義可知：Yi=Yi-1+Sifi(pi)，并定義Y0=0表示在未進行交易時在線交易者擁有的貨幣2的初始值為0．

2 隨機性決策算法

Xu 等對于上述模型運用最大最小定理提出了確定性算法AKD，其競爭比r為[8]：

本文運用基于風險的思想提出了隨機性算法RAKD，分析其競爭比，并通過實驗和確定性算法進行了對比，其中算法思想如下：

規則1只有當前的價格匯率用利潤函數計算后的值為迄今最大的時候才考慮將部分貨幣1兌換成貨幣2．

規則2每次將貨幣1兌換為貨幣2時，我們只兌換最少數目的貨幣1，使得即使以后的價格匯率一直保持最低時我們仍能保證競爭比為r．

與AKD相比較，這兩個規則表明隨機性算法RAKD不是一次性的完成交易，是每次兌換剩余貨幣1的一部分，而AKD則是接受唯一的價格一次性兌換所有的貨幣1．

注意，這兩個規則應用于除最后一個時間周期的所有其他時間周期，因為按照問題的表述，在線者必須在最后一個時間周期交易所有剩余貨幣1為貨幣2，并且只有當當前價格匯率經利潤函數計算后最大時才交易，所以假設：

rfn(m)≤f1(p1)

根據隨機性決策算法的思想及最壞情形分析，有如下引理成立．

證由于RAKD的競爭比是r，根據規則2，

由Di和Yi的定義，有

因為RAKD必須兌換滿足上述不等式的最少數目的貨幣1，可以看出上述不等式左邊是關于Si的遞減函數，因此替換不等式為等式，解關于Si的方程，得到

(1)

(2)

證畢．

解關于r的方程得到r的表達式為

進而可得到如下等式

為了計算出競爭比r的最大值，我們需要找到上式后半部分的最大值．令Xi=fi(pi)-fn(m)，則

此時，r只與f1(p1)和fk(pk)有關，即只與p1、pk及k有關．

于是可以解得對于2

(3)

證令t=f1(p1)，且有如下的替換

r(k,p1)對t求導，可以得到

考慮上式的分子，對于任意的v和k>1，方程

uk+fn(m)ku-fn(m)(k-1)v=0.

(4)

代入到(3)式，可以證明引理2，即

證畢．

證由上面的討論可知，r最大時對于任意的1

S2=S3=…=Sk，

且由(1)式和引理2有

該定理可通過(3)式，引理2，函數f的性質及單調性推導得出．

另外需要注意的是在實際應用中，如果在第i個時間周期，在線者獲得的價格匯率pi偏離了最壞情況序列，則在線者可以計算出以該匯率pi為第1個時間周期，在剩余n-i個交易周期的最優競爭比r′，并用該競爭比r′決定在第i個時間周期要兌換的貨幣1的數目．

3 實驗數值

觀察表1，可知隨著參數α的遞增，確定性算法的競爭比r1逐漸遞減．而根據定理1計算得出，在最壞情況下，隨機性算法(RAKD)的競爭比r2將保持為1.067 5不變．我們看到由于隨機性算法擴大了在線最壞情況序列的利潤，因此得到的競爭比不一定比確定性算法的競爭比小，所以對于上述的利潤函數得出如下的結論：當0<α≤0.124時，采用隨機性算法，當0.124<α<0.2時，采用確定性算法．并通過上述實驗可知，隨機性算法在一定情況下實現了算法競爭比的降低．

表1 競爭比結果(M=120，m=100，n=30)

4 總結

本文在文獻[8]的模型基礎上提出了基于風險的隨機性決策算法，分析證明了隨機性算法的競爭比，并通過實驗表明這一算法使得時間序列搜索問題的競爭比在一定情況下得到降低.在實際應用中，將根據具體的利潤函數決定采取確定性算法或隨機性算法．并且引入利潤函數的時間序列搜索模型是El-Yaniv等人[4]提出的問題模型的一般化，因此應用范圍較為廣泛．另外，對于時間序列搜索問題的確定性算法和隨機性算法的平均情況競爭比分析將是今后值得研究的問題．

參考文獻：

[1] BORODIN A, EL-YANIV R. Online computation and competitive analysis[M].Britain:Cambridge University press,1998.

[2] SLEATOR D D, TARJAN R E. Amortized efficiency of list update and paging rules [J]. Comm ACM, 1985, 28(2):202-208.

[3] EL-YANIV R, FIAT A, KARP R M,etal. Competitive analysis of financial games:proceedings of 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, PA, USA, 1992[C]. Pittsburgh:USA, 1992.

[4] EL-YANIV R, FIAT A, KARP R M,etal.Optimal search and one-way trading online algorithms[J]. Algorithmica,2001,30(1):101-139.

[5] AL-BINALI S. A risk-reward framework for the competitive analysis of financial games[J].Algorithmica,1999,25(1):99-115.

[6] LORENZ J, PANAGIOTOU K, STEGER A. Optimal algorithms for k-search with application in option pricing[J].Algorithmica,2008,55(2):311-328.

[7] DAMASCHKE P, HA P H, TSIGAS P. Online search with time varying price bounds[J]. Algorithmica,2007,55(4):619-642.

[8] XU Y, ZHANG W, ZHENG F. Optimal algorithms for the online time series search problem[J]. Theor Comput Sci,2009,doi:10.1016/j.tcs.2009.09.026.

[9] FUJIWARA H, IWAMA K, SEKIGUCHI Y. Average-case competitive analyses for one-way trading [J].J Comb Optim,2009,(published online).

[10] KAKADE S M, KEARNS M, MANSOUR Y,etal. Competitive algorithms for VWAP and limit order trading：EC′04 proceedings of the 5th ACM conference on electronic commerce, ACM, New York, NY, USA, 2004[C]. New York: USA, 2004.

[11] GWARTNEY J D, STROUP R L, SOBEL R S. Economics: private and public choice[M].王茂斌,吳宏,夏冰,譯.北京:機械工業出版社,2000.