Optimal search and one-way trading online algorithms
Optimal search and one-way trading online algorithms
复制标题
DOI：
10.1007/s00453-001-0003-0
复制
发表时间：
2001-05-01
期刊：
影响因子：
1.1
通讯作者：
Turpin, G
中科院分区：
文献类型：
--
作者：
El-Yaniv, R;Fiat, A;Turpin, G
本文研究了时间序列搜索和单向交易问题。在（时间序列）搜索问题中，参与者在一个顺序展开的序列中搜索最大（或最小）价格，每次一个价格。一旦在这个游戏中，玩家可以决定接受当前价格p，在这种情况下，游戏结束，玩家的收益是p。每天都会公布一个新的汇率，交易员必须决定根据当前汇率将多少美元兑换为日元。当交易者将他所有的美元财富都换成日元时，游戏就结束了，他的收益就是所获得的日元数量。任何（确定性的或随机的）单向交易算法都可以被视为随机搜索算法。使用的竞争比作为一个性能指标，我们确定这些问题的几个变种的最佳竞争性能。特别是，我们表明，一个简单的威胁为基础的战略是最佳的，我们确定其竞争比收益率，为现实值的问题参数，令人惊讶的低竞争ratis.We还考虑和分析了一个单向的交易游戏，对对手称为自然的在线玩家知道的概率分布的最大汇率和分布已选择的性质。最后，我们考虑了投资组合选择的一种特殊情况的一些应用，这种情况称为双向交易，交易者可以在现金和一种资产之间来回交易。
This paper is concerned with the time series search and one-way trading problems. In the (time series) search problem a player is searching for the maximum (or minimum) price in a sequence that unfolds sequentially, one price at a time. Once during this game the player can decide to accept the current price p in which case the game ends and the player's payoff is p. In the one-way trading problem a trader is given the task of trading dollars to yen. Each day, a new exchange rate is announced and the trader must decide how many dollars to convert to yen according to the current rate. The game ends when the trader trades his entire dollar wealth to yen and his payoff is the number of yen acquired.The search and one-way trading are intimately related. Any (deterministic or randomized) one-way trading algorithm can be viewed as a randomized search algorithm. Using the competitive ratio as a performance measure we determine the optimal competitive performance for several variants of these problems. In particular, we show that a simple threat-based strategy is optimal and we determine its competitive ratio which yields, for realistic values of the problem parameters, surprisingly low competitive ratios.We also consider and analyze a one-way trading game played against an adversary called Nature where the online player knows the probability distribution of the maximum exchange rate and that distribution has been chosen by Nature. Finally, we consider some applications for a Special case of portfolio selection called two-way trading in which the trader may trade back and forth between cash and one asset.