(3.238.7.202) 您好!臺灣時間:2021/02/26 14:46
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:翁興國
研究生(外文):Hsing-Kuo Wong
論文名稱:博奕論與線上計算之應用
論文名稱(外文):Game Theory with Application to On-Line Computation
指導教授:陳健輝陳健輝引用關係呂育道呂育道引用關係
指導教授(外文):Gen-Huey ChenYuh-Dauh Lyuu
學位類別:博士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:英文
論文頁數:132
中文關鍵詞:博奕論競爭分析法均勢策略競爭策略最佳競爭比值子賽局完美策略均等投資策略買後持有的投資問題
外文關鍵詞:Game theoryCompetitive analysisEquilibrium strategyCompetitive strategyOptimal competitive ratioSubgame perfect strategyDollar-Averaging strategyBuy-and-hold trading problem
相關次數:
  • 被引用被引用:0
  • 點閱點閱:237
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本篇論文的目的是研究線上博奕論與一個線上金融投資問題。在線上博奕論方面,我們研究競爭分析法與博奕論之間的理論對應,也研究在線上賽者擁有的各種策略與資訊結構下,隨機化是否能幫助線上賽者。在線上金融問題方面,我們研究買後持有的投資問題,此問題有三個變形:(1)對稱波動比率模型,(2)幾何布朗運動模型,及(3)有界日收益模型。由於競爭線上問題可以表示成一個線上賽局,線上賽局問題研究的結果可應用於線上金融投資問題。
在線上賽局問題方面,我們有以下結果:(1)澄清隱藏在線上博奕論背後的假設,(2)建立均勢策略、賽局值與競爭策略、最佳競爭比值之間的對應,(3)證明關於子賽局完美策略的定理,(4)推導出對有限的計劃賽局的一個具一般性的解決方法,(5)整理估計最佳競爭比值之下界的方法,及(6)在線上賽者擁有的各種策略與資訊結構下,證明數個關於隨機化是否能幫助線上賽者的定理。
在第一個投資問題變形方面,我們有以下結果:(1)推導出一個最佳的隨機門檻演算法RTA,(2)推導出一個緊湊的競爭比值的下界,及(3)證明RTA的競爭比值與該下界的比值是O(1),對一個很廣泛的問題參數範圍,實際的數值是小於1.8。
在第二個投資問題變形方面,我們有以下結果:(1)以模擬方式,證明RTA的平均競爭比值是小於2.2,及(2)證明RTA的交易成本很低。
在第三個投資問題變形方面,我們有以下結果:(1)推導出一個最佳的靜態投資策略BAL及精確的最佳競爭比值,(2)證明唯一性與最佳性,(3)證明BAL嚴格優於廣為流行的均等投資策略DA,(4)推導出一個動態投資策略SOS,它在非最差的情況下,可改善BAL,及(5)以1997台灣市場資料對BAL及DA作實驗。
The objective of this thesis is to study the theory of on-line games and an on-line financial trading problem. For the problems of on-line games, we study the theoretical correspondence between competitive analysis and game theory, and also study whether randomization can help the on-line player under various classes of strategies and information structures. The on-line financial problem under study is the buy-and-hold trading problem. We study three variants: (1) the model of symmetric fluctuation ratios, (2) the geometric Brownian motion model, and (3) the model of bounded daily returns. We apply the theoretical results developed for on-line games in the financial problems.
For the theory of on-line game, we have the results: (1) clarifying the assumptions behind the theory of on-line games, (2) establishing the correspondence between equilibrium strategies (game value, respectively) and competitive strategies (optimal competitive ratio, respectively), (3) proving theorems about subgame perfect strategies, (4) deriving a general solution for finite planning games, (5) summarizing methods for estimating the lower bound of the optimal competitive ratios, and (6) proving several theorems on whether randomization can help the on-line player under various classes of strategies and information structures.
For the first variant, we have the results: (1) deriving an optimal randomized threshold algorithm RTA, (2) deriving a tight lower bound, and (3) showing the ratio of RTA''s competitive ratio and the lower bound is O(1), in fact less than 1.8 for a wide range of problem parameters.
For the second variant, we have the results: (1) showing the ratio of expected return is less than 2.2 by simulation, (2) showing the transaction cost is very small.
For the third variant, we have the results: (1) deriving the optimal static trading strategy BAL and the exact optimal competitive ratio, (2) proving uniqueness and optimality, (3) showing that BAL beats the popular dollar-averaging strategy DA, (4) deriving a dynamic strategy SOS that improves BAL for non-worst-case inputs, and (5) performing experiments of BAL and DA for Taiwan''s market in 1997.
封面
1 Introduction
1.1 On-Line Algorithms and their Performance Measures
1.2 Problem Descriptions
1.3 Main Results
1.4Organization of the Thesis
2 Preliminaries
2.1 On-Line Problems
2.2 On-Line Games
3 Competitive Analysis and Game Theory
3.1 The Assumption of Rationality
3.2 Equilibrium Strategies
3.3 Subgame Perfect Strategies
3.4 General Solution to Finite Planning Games
3.5 Lower Bound for the Optimal Competitive Ratio against the Oblivious Adevrsary
3.6 Asymmetry between the On-line Player and the Adversary
4 Randomizationin the Adaptive Environment
4.1 Introduction
4.2 Problem Definition and Notations
4.3 Main Results
5 Competitive Analysis of Trading Problems
5.1 Introduction
5.2 An Optimal Randomized Threshold Algorithm
5.3 Optimality of Threshold Algorithms
6 Stochastic On-Line Financial Problems
6.1 Introduction
6.2 Algorithm Design and Simulation Setting
6.3 Simulation Results
7 Game-Theoretical Study of Trading Problems
7.1 Introduction
7.2 Optimal Static Buy-and-Hold Strategies
7.3 Does Real-Time Information Help
7.4 Empirical Analysis of Taiwan''s Market
8 Future Directions
Bibliography
[AAP93] B. Awerbuch, Y. Azar, and S. Plotkin.Throughput-competitive on-line routing. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pages 32--40, 1993.
[ABF+96] Y. Azar, Y. Bartal, E. Feuerstein, A. Fiat, S. Leonardi, and A. Rose n. On capital investment. In Proceedings of the 23rd International Colloquium on Automata, Languages, and Programming, 1996.
[ABK92] Y. Azar, A. Z. Broder, and A. R. Karlin. On-line load balancing. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 218--225, 1992.
[al-97] S. al-Binali. The competitive analysis of risk taking with application to online trading. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 336--344, 1997.
[Alb95] S. Albers. Improved randomized on-line algorithms for the list update problem. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 412--419, 1995.
[AMW95] M. Ajtai, N. Megiddo, and O. Waarts. Improved algorithms and analysis for secretary problems and generalizations. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 473--482, 1995.
[Apo74] Apo77 T. M. Apostol. Mathematical Analysis. Addison-Wesley, Reading, Mass., 2nd edition, 1974.
[Aum64] R. J. Aumann. Mixed and behavior strategies in infinite extensive games. In M. Dresher, L. S. Shapley, and A. W. Tucker, editors, Advances in Game Theory, volume I, pages 627--650. Princeton University Press, Princeton, 1964.
[Bar76] R. G. Bartle. The Elements of Real Analysis. Wiley, New York, 2nd edition, 1976.
[BDB94] S. Ben-David and A. Borodin. A new measure for the study of on-line algorithms. Algorithmica, 11(1):73--91, January 1994.
[BDBK+90] S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson. On the power of randomization in online algorithms. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 379--386, 1990.
[BDBK+94] S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11(1):2--14, January 1994.
[BEY97] A. Borodin and R. El-Yaniv. On randomization in online computations. In Proceedings of the 12nd Annual IEEE Conference on Computational Complexity, pages 226--238, 1997.
[BEY98] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, 1998.
[Bil68] P. Billingsley. Convergence of Probability Measures. John Wiley & Sons, New York, 1968.
[BIRS91] A. Borodin, S. Irani, P. Raghavan, and B. Schieber. Competitive paging with locality of reference. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 249--259, 1991.
[BR96] M. Baxter and A. Rennie. Financial Calculus: an Introduction to Derivative Pricing. Cambridge University Press, Cambridge, 1996.
[BS96] A. N. Borodin and P. Salminen. Handbook of Brownian Motion-Facts and Formulae. Birkhauser Verlag, Basel, 1996.
[CCEY+95] A. Chou, J. Cooperstock, R. El-Yaniv, M. Klugerman, and T. Leighton. The statistical adversary allows optimal money-making trading strategies. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 467--476, 1995.
[CD96] R. Cairoli and Robert C. Dalang. Sequential Stochastic Optimization. John Wiley & Sons, New York, 1996.
[CFH+93] N. Cesa-Bianchi, Y. Freund, D. P. Helmbold, D. Haussler, R. E. Schapire, and M. K. Warmuth. How to use expert advice. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993.
[Chu74] K. L. Chung. A Course in Probability Theory. Academic Press, New York and London, 2nd edition, 1974.
[CKLW99] G. H. Chen, M. Y. Kao, Y. D. Lyuu, and H. K. Wong. Optimal buy-and-hold strategies for financial markets with bounded daily returns. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 119--128, 1999.
[CMRS64] Y. S. Chow, S. Moriguti, H. Robbins, and S. M. Samuels. Optimal selection based on relative rank (the secretary problem). Israel Journal of Mathematics, 2:81--90, 1964.
[CO96] T. M. Cover and E. Ordentlich. Universal portfolios with side information. IEEE Transactions on Information Theory, 42(2), March 1996.
[Cov91] T. M. Cover. Universal portfolio. Mathematical Finance, 1:1--29, 1991.
[CZ96] K. P. Edwin Chong and Stanislaw H. Zak. An Introduction to Optimization. John Wiley & Sons, New York, 1996.
[DKP91] X. Deng, T. Kameda, and C. H. Papadimitriou. How to learn an unknown environment. In Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, pages 298--303, 1991.
[DM91] X. Deng and S. Mahajan. Infinite games: randomization, computability, and applications to online problems. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 289--298, 1991.
[DM97] X. Deng and S. Mahajan. The cost of derandomization: computability or competitiveness. SIAM Journal on Computing, 26:786--802, 1997.
[DP90] X. Deng and C. Papadimitriou. Exploring an unknown graph. In Proceedings of the 31st IEEE Symposium Foundations of Computer Science, pages 355--361, 1990.
[Duf96] D. Duffie. Dynamic Asset Pricing Theory. Princeton University Press, Princeton, 1996.
[EY96] R. El-Yaniv. There are infinitely many competitive-optimal online list accessing algorithms. Manuscript, May 1996.
[EY98] R. El-Yaniv. Competitive solutions for online financial problems. ACM Computing Surveys, 30:28--69, 1998.
[EYFKT92] R. El-Yaniv, A. Fiat, R. Karp, and G. Turpin. Competitive analysis of financial games. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 327--333, 1992.
[EYFKT97] R. El-Yaniv, A. Fiat, R. M. Karp, and G. Turpin. Optimal search and one-way trading online algorithms. Manuscript, 1997.
[EYKL93] R. El-Yaniv, R. Kaniel, and N. Linial. On the equipment rental problem. To be published, August 1993.
[Fre83] P. R. Freeman. The secretary problem and its extensions. International Statistical Review, 51:189--206, 1983.
[FS96] Y. Freund and R. Schapire. Game theory, on-line prediction and boosting. In Proceedings of the 9th Annual Conference on Computational Learning Theory, pages 325--332, 1996.
[FT91] D. Fudenberg and J. Tirole. Game Theory. MIT Press, Cambridge, 1991.
[Gea94] J. Geanakoplos. Common knowledge. In R. Aumann and S. Hart, editors, Handbook of Game Theory, volume 2, pages 1437--1496. Elsevier, Amsterdam, 1994.
[Har92] S. Hart. Games in extensive and strategic forms. In R. Aumann and S. Hart, editors, Handbook of Game Theory, volume 1, pages 19--40. Elsevier, Amsterdam, 1992.
[Hoc97] D. S. Hochbaum. Approximation Algorithms for NP-Hard Problems. PWS Publishing, Boston, 1997.
[Hul97] J. C. Hull. Options, Futures, and Other Derivatives. Prentice-Hall, Upper Saddle River, 3rd edition, 1997.
[Ira94] S. Irani. Coloring inductive graphs on-line. Algorithmica, 11(1):53--72, January 1994.
[Isb57] J. Isbell. Finitary games. In M. Dresher, A. Tucker, and P. Wolfe, editors, Contributions to the Theory of Games, volume III, pages 79--96. Princeton University Press, Princeton, 1957.
[KMRS88] A. R. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator. Competitive snoopy caching. Algorithmica, 3:79--119, 1988.
[KP94] E. Koutsoupias and C. H. Papadimitriou. Beyond competitive analysis. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, pages 394--400, 1994.
[KPR94] A. Karlin, S. Phillips, and P. Raghavan. Markov paging. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, pages 208--217, 1994.
[KRT93] M. Y. Kao, J. H. Reif, and S. R. Tate. Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 441--447, 1993.
[KT91] H. A. Kierstead and W. T. Trotter. On-line graph coloring. In On-Line Algorithms: Proceedings of a DIMACS Workshop, pages 85--92. American Mathematical Society, 1991.
[KT97] M. Y. Kao and S. R. Tate. On-line difference maximization. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 175--182, 1997.
[Kuh53] H. Kuhn. Extensive games and the problem of information. In Contributions to the Theory of Games, volume 2, pages 193--216. Princeton University Press, Princeton, 1953.
[LR57] R. D. Luce and H. Raiffa. Games and Decisions: Introduction and Critical Survey. John Wiley & Sons, New York, 1957.
[Lyu99] Y. D. Lyuu. Financial Engineering and Computation: Principles, Mathematics, Algorithms. To be published, 1999.
[MMS88] M. S. Manasse, L. A. McGeoch, and D. D. Sleator. Competitive algorithms for online problems. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 322--333, 1988.
[MR95] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, 1995.
[Nef96] S. N. Neftci. An Introduction to the Mathematics of Financial Derivatives. Academic Press, New York, 1996.
[OC96] E. Ordentlich and T. M. Cover. On-line portfolio selection. In Proceedings of the 1996 Conference on Computational Learning Theory, pages 310--313, 1996.
[OM75] B. Ostle and R. W. Mensing. Statistics in Research. The Iowa State University Press, Ames, 3rd edition, 1975.
[OR94] M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press, Cambridge, 1994.
[Put94] M. Puterman. Markov Decision Processes: Discrete Dynamic Programming. John Wiley & Sons, New York, 1994.
[PZ96] L. A. Petrosjan and N. A. Zenkevich. Game Theory. World Scientific, Singapore, 1996.
[Rag92] P. Ragahavan. A statistical adversary for on-line algorithms. In L. A. McGeoch and D. D. Sleator, editors, On-Line Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 79--84, Providence, 1992. American Mathematical Society.
[Rag94] T. Raghavan. Zero-sum two-person games. In R. Aumann and S. Hart, editors, Handbook of Game Theory, volume 2, pages 735--759. Elsevier, Amsterdam, 1994.
[RS89] P. Raghavan and M. Snir. Memory vs. randomization in on-line algorithms. In Proceedings of the 16th International Colloquium on Automata, Languages, and Programming, pages 687--703, 1989. Springer-Verlag Lecture Notes in Computer Science No. 372.
[RS94] P. Raghavan and M. Snir. Memory vs. randomization in on-line algorithms. IBM Journal of Research and Development, 38:683--707, 1994.
[Rub98] A. Rubinstein. Modeling Bounded Rationality. The MIT Press, Cambridge, 1998.
[SAB95] W. F. Sharpe, G. J. Alexander, and J. V. Bailey. Investments. Prentice-Hall, Upper Saddle River, 5th edition, 1995.
[vD91] E. van Damme. Stability and Perfection of Nash Equilibria. Springer-Verlag, New York, 2nd edition, 1991.
[WHD95] P. Wilmott, S. Howison, and J. Dewynne. The Mathematics of Financial Derivatives. Cambridge University Press, Cambridge, 1995.
[WLC98a] H. K. Wong, Y. D. Lyuu, and G. H. Chen. Optimal on-line one-way trading algorithm with bounded fluctuation ratios. Manuscript, 1998.
[WLC98b] H. K. Wong, Y. D. Lyuu, and G. H. Chen. Randomized on-line one-way trading algorithm in the geometric brownian motion exchange rate model. In Proceedings International Symposium on Intelligent Data Engineering and Learning (IDEAL''98), pages 106--112. Springer, 1998.
[Yao77] A. C.-C. Yao. Probabilistic computations: Towards a unified measure of complexity. In Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science, pages 222--227, 1977.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔