CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

One-Way Trading with Time-Varying Exchange Rate Bounds

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)) ; Phuong Ha (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers)) ; Philippas Tsigas (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers))
Göteborg : Chalmers University of Technology, 2005. - 14 s.
[Rapport]

One-way trading is a basic online problem in finance. Since its optimal solution is given by a simple formula (however with difficult analysis), the problem is attractive as a target to which other practical online problems can be transformed. However, there are still natural online problems that do not fit in the known variants of one-way trading. We present some new models where the bounds of exchange rates are not constant but vary with time in certain ways. The first model, where the (logarithmic) exchange rate has limited decay speed, arises from an issue in distributed data structures, namely to maximize the (appropriately defined) freshness of values in concurrent objects. For this model we prove a lower bound on the competitive ratio which is nearly optimal, i.e., up to a small constant factor. Clearly, the lower bound holds also against stronger adversaries. Then, we give an optimal algorithm in a model where only the maximal allowed exchange rate decreases with time, but the actual exchange rates may jump arbitrarily within this frame. We have chosen this more powerful adversary model afterwards because some applications does not make use of the limited decay speed. In fact, we adapt the optimal threat-based algorithm of El-Yaniv et al. (2001) to our case. Our numerical experiments suggest that this algorithm is still not too far from the lower bound for the weaker adversary. This is explained by the observation that slowly increasing exchange rates seem to be the worst case for the online player.

Nyckelord: algorithms and data structures, distributed computing, online algorithms, one-way trading



Denna post skapades 2006-08-25. Senast ändrad 2015-02-11.
CPL Pubid: 7608

 

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)
Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)
Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers) (2005-2007)

Ämnesområden

Information Technology

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:


Reactive Concurrent Data Structures and Algorithms for Synchronization


Ingår i serie

Technical report - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University 2005:17