基于竞争差分析的占线单向交易策略
|
摘要
针对交易者事先仅知道价格波动范围的占线单向交易问题,基于Savage后悔值准则提出了竞争差分析方法,通过引入一个假想的能够控制价格的"对手"将原来的单人决策问题转化为双人零和博弈问题.与竞争比分析相比,竞争差分析由于目标函数的数学形式更简单,因而可以直接采用逆向归纳法求解获得使最大后悔值(竞争差)最小化的稳健的占线交易策略,并找出对于交易者而言所有可能的最糟糕情况,而不必像竞争比分析那样需要事先猜测最优占线策略的特征;此外,数值模拟结果表明,基于竞争差分析的占线算法更节省计算时间,且在解决收益最大化问题时不像竞争比分析那样过于保守,一般具有更好的期望绩效.
How to make online trading decisions in one-way trading when only the range of prices in the future is known beforehand? This paper applies Savage's mini-max regret criterion and proposes a method of competitive difference analysis(CDA). The CDA introduces an imaginary adversary who controls the price sequences,thus transforming the original one-person decision-making problem into a two-person zero-sum game.Compared with the widely used method of competitive ratio analysis(CRA) which depends heavily on prior intuition,the CDA can directly obtain the optimal online trading strategy and all the possible worst-case scenarios for the trader via backward induction. In addition,numerical experiments show that the online algorithm based on CDA can save calculation time and that it outperforms the online algorithm based on CRA when solving revenue-maximization problems because it is less conservative.
How to make online trading decisions in one-way trading when only the range of prices in the future is known beforehand? This paper applies Savage's mini-max regret criterion and proposes a method of competitive difference analysis(CDA). The CDA introduces an imaginary adversary who controls the price sequences,thus transforming the original one-person decision-making problem into a two-person zero-sum game.Compared with the widely used method of competitive ratio analysis(CRA) which depends heavily on prior intuition,the CDA can directly obtain the optimal online trading strategy and all the possible worst-case scenarios for the trader via backward induction. In addition,numerical experiments show that the online algorithm based on CDA can save calculation time and that it outperforms the online algorithm based on CRA when solving revenue-maximization problems because it is less conservative.
引文
[1]Lippman S A,Mc Call J J.The economics of job search:A survey[J].Economic Inqury,1976,14(6):155-189.
[2]Lippman S A,Mc Call J J.The Economics of Uncertainty:Selected Topics and Probabilistic Methods[M]//Ed.Arrow K J,Intriligator M D.Handbook of Mathematical Economics I,Amsterdam:North-Holland,1981:211-284.
[3]El-Yaniv R,Fiat A,Karp R M,et al.Optimal search and one-way trading online algorithms[J].Algorithmica,2001,30(1):101-139.
[4]Sleator D,Tarjan R E.Amortized efficiency of list update and paging rules[J].Communications of the ACM,1985,28(2):202-208.
[5]Chen G H,Kao M Y,Lyuu Y D,et al.Optimal buy-and-hold strategies for financial markets with bounded daily returns[J].SIAM Journal on Computing,2001,31(2):447-459.
[6]Zhang W M,Xu Y F,Zheng F F,et al.Optimal algorithms for online time series search and one-way trading with interrelated prices[J].Journal of Combinatorial Optimization,2012,23(2):159-166.
[7]Larsen K S,Whlk S.Competitive analysis of the online inventory problem[J].European Journal of Operational Research,2010,207(2):685-696.
[8]Dai W,Jiang Q,Feng Y.A note:An improved upper bound for the online inventory problem with bounded storage and order costs[J].European Journal of Operational Research,2016,249(2):628-630.
[9]Damaschke P,Ha P H,Tsigas P.Online search with time-varying price bounds[J].Algorithmica,2009,55(4):619-642.
[10]Xu Y F,Zhang W M,Zheng F F.Optimal algorithms for the online time series search problem[J].Theoretical Computer Science,2011,412(3):192-197.
[11]Lorenz J,Panagiotou K,Steger A.Optimal algorithms for k-search with application in option pricing[J].Algorithmica,2009,55:311-328.
[12]Zhang W M,Xu Y F,Zheng F F,et al.Online algorithms for the general k-search problem[J].Information Processing Letters,2011,111(14):678-682.
[13]Zhang W M,Xu Y F,Zheng F F,et al.Online algorithms for the multiple time series search problem[J].Computers&Operations Research,2012,39(5):929-938.
[14]倪冠群,徐寅峰,徐玖平.航空收益管理价格和座位在线联合控制策略[J].管理科学学报,2014,17(7):10-21.Ni Guanqun,Xu Yinfeng,Xu Jiuping.Competitive analysis of revenue management:Online joint pricing and booking strategies[J].Journal of Management Sciences in China,2014,17(7):10-21.(in Chinese)
[15]张卫国,张永,徐维军,等.随机选择设备获得方式的可折旧设备在线租赁[J].管理科学学报,2013,16(4):1-7.Zhang Weiguo,Zhang Yong,Xu Wejun,et al.Online leasing of depreciable equipment based on randomization of obtaining methods[J].Journal of Management Sciences in China,2013,16(4):1-7.(in Chinese)
[16]胡茂林,徐维军,刘幼珠.存在市场利率的连续松弛多重在线租赁问题[J].管理科学学报,2014,17(9):29-39.Hu Maolin,Xu Weijun,Liu Youzhu.Multiple online leasing problem of continuous relaxation with market interest rate[J].Journal of Management Sciences in China,2014,17(9):29-39.(in Chinese)
[17]Dorrigiv R,López-Ortiz A.A survey of performance measures for online algorithms[J].SIGACT News(ACM Special Interest Group on Automata and Computability Theory),2005,36(3):67-81.
[18]Boyar J,Larsen K S,Maiti A.A comparison of performance measures via online search[J].Theoretical Computer Science,2011,532(3):2-13.
[19]Fujiwara H,Iwama K,Sekiguchi Y.Average-case competitive analyses for one-way trading[J].Journal of Combinatorial Optimization,2011,21(1):83-107.
[20]Mohr E,Schmidt G.How much is it worth to know the future in online conversion problems[J].Discrete Applied Mathematics,2013,161(10/11):1546-1555.
[21]Mohr E,Ahmad I,Schmidt G.Online algorithms for conversion problems:A survey[J].Surveys in Operations Research and Management Science,2014,19(2):87-104.
[2]Lippman S A,Mc Call J J.The Economics of Uncertainty:Selected Topics and Probabilistic Methods[M]//Ed.Arrow K J,Intriligator M D.Handbook of Mathematical Economics I,Amsterdam:North-Holland,1981:211-284.
[3]El-Yaniv R,Fiat A,Karp R M,et al.Optimal search and one-way trading online algorithms[J].Algorithmica,2001,30(1):101-139.
[4]Sleator D,Tarjan R E.Amortized efficiency of list update and paging rules[J].Communications of the ACM,1985,28(2):202-208.
[5]Chen G H,Kao M Y,Lyuu Y D,et al.Optimal buy-and-hold strategies for financial markets with bounded daily returns[J].SIAM Journal on Computing,2001,31(2):447-459.
[6]Zhang W M,Xu Y F,Zheng F F,et al.Optimal algorithms for online time series search and one-way trading with interrelated prices[J].Journal of Combinatorial Optimization,2012,23(2):159-166.
[7]Larsen K S,Whlk S.Competitive analysis of the online inventory problem[J].European Journal of Operational Research,2010,207(2):685-696.
[8]Dai W,Jiang Q,Feng Y.A note:An improved upper bound for the online inventory problem with bounded storage and order costs[J].European Journal of Operational Research,2016,249(2):628-630.
[9]Damaschke P,Ha P H,Tsigas P.Online search with time-varying price bounds[J].Algorithmica,2009,55(4):619-642.
[10]Xu Y F,Zhang W M,Zheng F F.Optimal algorithms for the online time series search problem[J].Theoretical Computer Science,2011,412(3):192-197.
[11]Lorenz J,Panagiotou K,Steger A.Optimal algorithms for k-search with application in option pricing[J].Algorithmica,2009,55:311-328.
[12]Zhang W M,Xu Y F,Zheng F F,et al.Online algorithms for the general k-search problem[J].Information Processing Letters,2011,111(14):678-682.
[13]Zhang W M,Xu Y F,Zheng F F,et al.Online algorithms for the multiple time series search problem[J].Computers&Operations Research,2012,39(5):929-938.
[14]倪冠群,徐寅峰,徐玖平.航空收益管理价格和座位在线联合控制策略[J].管理科学学报,2014,17(7):10-21.Ni Guanqun,Xu Yinfeng,Xu Jiuping.Competitive analysis of revenue management:Online joint pricing and booking strategies[J].Journal of Management Sciences in China,2014,17(7):10-21.(in Chinese)
[15]张卫国,张永,徐维军,等.随机选择设备获得方式的可折旧设备在线租赁[J].管理科学学报,2013,16(4):1-7.Zhang Weiguo,Zhang Yong,Xu Wejun,et al.Online leasing of depreciable equipment based on randomization of obtaining methods[J].Journal of Management Sciences in China,2013,16(4):1-7.(in Chinese)
[16]胡茂林,徐维军,刘幼珠.存在市场利率的连续松弛多重在线租赁问题[J].管理科学学报,2014,17(9):29-39.Hu Maolin,Xu Weijun,Liu Youzhu.Multiple online leasing problem of continuous relaxation with market interest rate[J].Journal of Management Sciences in China,2014,17(9):29-39.(in Chinese)
[17]Dorrigiv R,López-Ortiz A.A survey of performance measures for online algorithms[J].SIGACT News(ACM Special Interest Group on Automata and Computability Theory),2005,36(3):67-81.
[18]Boyar J,Larsen K S,Maiti A.A comparison of performance measures via online search[J].Theoretical Computer Science,2011,532(3):2-13.
[19]Fujiwara H,Iwama K,Sekiguchi Y.Average-case competitive analyses for one-way trading[J].Journal of Combinatorial Optimization,2011,21(1):83-107.
[20]Mohr E,Schmidt G.How much is it worth to know the future in online conversion problems[J].Discrete Applied Mathematics,2013,161(10/11):1546-1555.
[21]Mohr E,Ahmad I,Schmidt G.Online algorithms for conversion problems:A survey[J].Surveys in Operations Research and Management Science,2014,19(2):87-104.