Abstrakt. Detta dokument handlar om tidsseriesökning och problem med enkelriktad handel. I (tidsserien) sökproblem en spelare söker efter det maximala (eller lägsta) priset i en sekvens som utvecklas sekventiellt, ett pris i taget. En gång under detta spel kan spelaren besluta att acceptera det aktuella priset p i vilket fall spelet slutar och spelarens payoff är p. I enkelriktad handel problem en näringsidkare ges uppgiften att handla dollar till yen. Varje dag, en ny växelkurs tillkännages och näringsidkaren måste bestämma hur många dollar att konvertera till yen enligt den nuvarande kursen. Spelet slutar när näringsidkaren byter hela sin dollar rikedom till yen och hans vinst är antalet yen förvärvade. Sökandet och enkelriktad handel är intimt relaterade. Alla (deterministiska eller randomiserade) envägshandelsalgoritm kan ses som en randomiserad sökalgoritm. Med hjälp av konkurrensförhållandet som resultatmått bestämmer vi den optimala konkurrenskraften för flera varianter av dessa problem. I synnerhet visar vi att en enkel hotbaserad strategi är optimal och vi bestämmer dess konkurrensförhållande som, för realistiska värden på problemparametrarna, ger förvånansvärt låga konkurrensförhållanden. Vi överväger och analyserar också en enkelriktad handel spel som spelas mot en motståndare som heter Nature där online-spelaren vet sannolikhetsfördelningen av den maximala växelkursen och att distributionen har valts av naturen. Slutligen överväger vi vissa ansökningar för ett specialfall av portföljval som kallas tvåvägshandel där näringsidkaren kan handla fram och tillbaka mellan kontanter och en tillgång.
I nära samband med resultaten av detta dokument undersökte REF det klassiska problemet med enkelriktad handel och utarbetade konkurrenskraftiga online-algoritmer med optimalt konkurrensförhållande.
Optimal Search and One-Way Trading Online Algorithms
{'venue': 'FOCS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}