Competitive analysis of bi-directional non-preemptive conversion

Günter Schmidt ()
Additional contact information
Günter Schmidt: Saarland University

Journal of Combinatorial Optimization, 2017, vol. 34, issue 4, No 7, 1096-1113

Abstract: Abstract In an online conversion problem a player is converting one asset into another, e.g. dollars to yen, based on a finite sequence of unknown future conversion rates. When a new rate is announced the player must decide how many dollars (yen) to convert to yen (dollars) according to this rate. Conversion is over when the last rate has appeared. The objective is to maximize terminal wealth after conversion. In uni-directional conversion dollars are converted to yen and in bi-directional conversion not only dollars to yen but also yen to dollars may be converted. If all current wealth has to be converted at one rate we call the problem non-preemptive; if parts of the current wealth can be converted at one rate we call it preemptive. We assume that lower and upper bounds on conversion rates are given. Uni-directional preemptive and non-preemptive and bi-directional preemptive conversion is investigated in El Yaniv et al. (Proceeding 33rd annual symposium on foundations of computer science, pp 327–333, 1992, Algorithmica 30:101–139, 2001). Their results for bi-directional preemptive conversion are improved by Dannoura and Sakurai (Inf Process Lett 66:27–33, 1998). The suggested improvement is conjectured not to be optimal for bi-directional preemptive conversion. There are no results for optimal bi-directional non-preemptive conversion. We investigate the problem of bi-directional non-preemptive online conversion. We present lower bounds, upper bounds and an optimal algorithm to solve the problem. Moreover, we prove that the algorithm of Dannoura and Sakurai 1998 is not optimal for bi-directional preemptive conversion.

Keywords: Financial games; Conversion problem; Online algorithms; Competitive analysis; Bi-directional conversion; One-way trading; Time series search; 68W27; 68W40; 68Q25 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0131-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:34:y:2017:i:4:d:10.1007_s10878-017-0131-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0131-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().