Best Possible Algorithms for One-Way Trading with Only the Maximum Fluctuation Ratio Available
Summary :
In Variant 4 of the one-way trading game [El-Yaniv, Fiat, Karp, and Turpin, 2001], a player has one dollar at the beginning and wants to convert it to yen only by one-way conversion. The exchange rate is guaranteed to fluctuate between m and M, and only the maximum fluctuation ratio φ = M/m is informed to the player in advance. The performance of an algorithm for this game is measured by the competitive ratio. El-Yaniv et al. derived the best possible competitive ratio over all algorithms for this game. However, it seems that the behavior of the best possible algorithm itself has not been explicitly described. In this paper we reveal the behavior of the best possible algorithm by solving a linear optimization problem. The behavior turns out to be quite different from that of the best possible algorithm for Variant 2 in which the player knows m and M in advance.
- Publication
- IEICE TRANSACTIONS on Information Vol.E107-D No.3 pp.278-285
- Publication Date
- 2024/03/01
- Publicized
- 2023/10/23
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2023FCP0002
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science — Foundations of Computer Science and their New Trends —)
- Category
Authors
Hiroshi FUJIWARA
Shinshu University
Keiji HIRAO
Shinshu University
Hiroaki YAMAMOTO
Shinshu University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroshi FUJIWARA, Keiji HIRAO, Hiroaki YAMAMOTO, "Best Possible Algorithms for One-Way Trading with Only the Maximum Fluctuation Ratio Available" in IEICE TRANSACTIONS on Information,
vol. E107-D, no. 3, pp. 278-285, March 2024, doi: 10.1587/transinf.2023FCP0002.
Abstract: In Variant 4 of the one-way trading game [El-Yaniv, Fiat, Karp, and Turpin, 2001], a player has one dollar at the beginning and wants to convert it to yen only by one-way conversion. The exchange rate is guaranteed to fluctuate between m and M, and only the maximum fluctuation ratio φ = M/m is informed to the player in advance. The performance of an algorithm for this game is measured by the competitive ratio. El-Yaniv et al. derived the best possible competitive ratio over all algorithms for this game. However, it seems that the behavior of the best possible algorithm itself has not been explicitly described. In this paper we reveal the behavior of the best possible algorithm by solving a linear optimization problem. The behavior turns out to be quite different from that of the best possible algorithm for Variant 2 in which the player knows m and M in advance.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2023FCP0002/_p
Copy
@ARTICLE{e107-d_3_278,
author={Hiroshi FUJIWARA, Keiji HIRAO, Hiroaki YAMAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Best Possible Algorithms for One-Way Trading with Only the Maximum Fluctuation Ratio Available},
year={2024},
volume={E107-D},
number={3},
pages={278-285},
abstract={In Variant 4 of the one-way trading game [El-Yaniv, Fiat, Karp, and Turpin, 2001], a player has one dollar at the beginning and wants to convert it to yen only by one-way conversion. The exchange rate is guaranteed to fluctuate between m and M, and only the maximum fluctuation ratio φ = M/m is informed to the player in advance. The performance of an algorithm for this game is measured by the competitive ratio. El-Yaniv et al. derived the best possible competitive ratio over all algorithms for this game. However, it seems that the behavior of the best possible algorithm itself has not been explicitly described. In this paper we reveal the behavior of the best possible algorithm by solving a linear optimization problem. The behavior turns out to be quite different from that of the best possible algorithm for Variant 2 in which the player knows m and M in advance.},
keywords={},
doi={10.1587/transinf.2023FCP0002},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Best Possible Algorithms for One-Way Trading with Only the Maximum Fluctuation Ratio Available
T2 - IEICE TRANSACTIONS on Information
SP - 278
EP - 285
AU - Hiroshi FUJIWARA
AU - Keiji HIRAO
AU - Hiroaki YAMAMOTO
PY - 2024
DO - 10.1587/transinf.2023FCP0002
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E107-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2024
AB - In Variant 4 of the one-way trading game [El-Yaniv, Fiat, Karp, and Turpin, 2001], a player has one dollar at the beginning and wants to convert it to yen only by one-way conversion. The exchange rate is guaranteed to fluctuate between m and M, and only the maximum fluctuation ratio φ = M/m is informed to the player in advance. The performance of an algorithm for this game is measured by the competitive ratio. El-Yaniv et al. derived the best possible competitive ratio over all algorithms for this game. However, it seems that the behavior of the best possible algorithm itself has not been explicitly described. In this paper we reveal the behavior of the best possible algorithm by solving a linear optimization problem. The behavior turns out to be quite different from that of the best possible algorithm for Variant 2 in which the player knows m and M in advance.
ER -
English
