A general solution is presented for any finite request-answer game to derive its optimal competitive ratio and optimal randomized on-line algorithm against the oblivious adversary. The solution is based on game theory. We then apply the framework to the practical buy-and-hold trading problem and find the exact optimal competitive ratio and an optimal randomized on-line algorithm. We also prove the uniqueness of the solution.
|Original language||English (US)|
|Number of pages||10|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 1999|
|Event||Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA|
Duration: May 1 1999 → May 4 1999
ASJC Scopus subject areas