معاملات آنلاین بهینه دو طرفه با تعداد محدود معاملات

ما یک مشکل معاملات دو طرفه را در نظر می گیریم ، جایی که سرمایه گذاران سهام را خریداری و می فروشند که قیمت آن در محدوده خاصی حرکت می کند. طبیعتاً آنها می خواهند سود خود را به حداکثر برسانند. سرمایه گذاران می توانند تا معاملات K را انجام دهند ، جایی که هر تجارت باید مبلغ کامل را در بر بگیرد. ما الگوریتم های بهینه را برای سه مدل مختلف ارائه می دهیم که در دانش نحوه نوسان قیمت متفاوت است. در مدل اول ، حداقل و حداکثر مرزهای M و M وجود دارد. ما ابتدا یک حد پایین بهینه از ( varphi ) (که در آن ( varphi = m/m )) را در نسبت رقابتی برای یک تجارت نشان می دهیم ، که محدود به الگوریتم های بی اهمیت است. شاید با کمال تعجب ، وقتی بیش از یک تجارت را در نظر می گیریم ، می توانیم الگوریتم بهتری ارائه دهیم که فقط یک عامل ( varphi ^) (به جای ( varphi )) در هر تجارت اضافی از دست می دهد. به طور خاص ، برای معاملات K الگوریتم نسبت رقابتی ( varphi ^) دارد. علاوه بر این ، ما نشان می دهیم که این نسبت با دادن محدودیت پایین تر ، بهترین امکان را دارد. در مدل دوم ، M و M از قبل مشخص نیستند ، و فقط ( varphi ) شناخته شده است. ما نشان می دهیم که این تنها یک عامل اضافی از ( varphi ^) برای ما هزینه می کند ، یعنی هر دو مرز فوقانی و تحتانی ( varphi ^) می شوند. سرانجام ، ما مدل بازگشت روزانه محدود را در نظر می گیریم که در آن به جای محدودیت جهانی ، نوسان از یک روز به روز دیگر محدود است ، و دوباره الگوریتم های بهینه می دهیم ، و جالب اینکه یکی از آنها شبیه استراتژی های معاملاتی مشترک است که شامل محدودیت های از دست دادن است.

روی نسخه خطی کار می کنید؟

از رایج ترین اشتباهات خودداری کنید و نسخه خطی خود را برای ویراستاران ژورنال آماده کنید.

معرفی

مدل

We consider a scenario commonly faced by investors. The price of a stock varies over time. In this paper we use a ‘day’ as the smallest unit of time, so there is one new price each day. Let p ( i ) be the price at day i . The investor has some initial amount of money. Over a time horizon of finite duration T , the investor wants to make a bounded number of trades of this one stock. Each trade ( b , s ) consists of a buy transaction at day b , followed by a sell transaction at day s where (s>B ).(بنابراین یک تجارت از دو معاملات تشکیل شده است.) هر دو معاملات "همه" هستند: هنگام خرید ، سرمایه گذار از تمام پول های موجود استفاده می کند و هنگام فروش ، تمام سهام موجود در آن در حال حاضر فروخته می شود. قبل از انجام خرید بعدی باید یک فروش انجام شود. همچنین ، هیچ فروش کوتاهی مجاز نیست ، یعنی اگر سرمایه گذار در حال حاضر سهام خود را در اختیار نداشته باشد ، نمی تواند فروش داشته باشد. با رسیدن پایان افق زمانی ، یعنی در روز گذشته ، هیچ خریدی مجاز نیست و سرمایه گذار باید تمام سهام را که هنوز هم با قیمت روز به پول نقد باز می گردند ، بفروشد.

تعدادی از منطقی برای در نظر گرفتن تعداد محدودی از معاملات و/یا معاملات باید تمام پول های موجود را در نظر بگیرند. سرمایه گذاران فردی و آماتور به طور معمول نمی خواهند به دلیل هزینه های بالای معاملات ، معاملات مکرر انجام دهند. غالباً هزینه های معاملات دارای یک مؤلفه ثابت هستند (به عنوان مثال ، یک مبلغ ثابت یا حداقل تعرفه در هر معامله ، صرف نظر از مبلغ معاملات) که هزینه های معاملات را به طور نامتناسب برای معاملات کوچک بالا می برد. تجارت مکرر همچنین نیاز به نظارت مداوم بر بازارهایی دارد که ممکن است سرمایه گذاران آماتور وقت و منابع لازم را برای آن نداشته باشند. غالباً آنها فقط می خواهند اوراق بهادار سرمایه گذاری خود را هر از چند گاهی تغییر دهند. همچنین ، برای سرمایه گذاران با پول اندک در دسترس ، تقسیم آنها به گلدان های کوچکتر پول ، در کسری های دلخواه ، همانطور که توسط برخی از الگوریتم ها لازم است ، امکان پذیر یا معقول نیست. ظرافت افق زمانی (و این که طول آن احتمالاً ناشناخته است) با موقعیت هایی مطابقت دارد که به عنوان مثال ممکن است یک سرمایه گذار مجبور به فروش و ترک بازار شود و به عنوان مثال ، به عنوان مثال نیاز غیر منتظره به پول در جای دیگر داشته باشد.

هر تجارت با قیمت خرید p (b) و قیمت فروش p (s) سود p (s) / p (b) را به دست می آورد. این نشان می دهد که سرمایه گذار پس از تجارت در صورت سرمایه گذاری در ابتدا 1 دلار سرمایه گذاری کرده است. توجه داشته باشید که این یک نسبت است و می تواند کمتر از 1 باشد ، به این معنی که ضرر وجود دارد ، اما ما هنوز هم به عنوان "سود" به آن اشاره خواهیم کرد. اگر یک سری معاملات انجام شود ، سود کلی یا بازگشت الگوریتم محصول سود هر یک از معاملات فردی است. این به درستی نشان دهنده این واقعیت است که تمام پول پس از هر تجارت در زمان دیگری دوباره سرمایه گذاری می شود.

از آنجا که سرمایه گذاران بدون اطلاع از قیمت سهام آینده تصمیم گیری می کنند ، مشکل در ماهیت آنلاین است. ما عملکرد الگوریتم های آنلاین را با تجزیه و تحلیل رقابتی اندازه گیری می کنیم ، یعنی با مقایسه آن با الگوریتم آفلاین بهینه که توالی قیمت را از قبل می داند و بنابراین می تواند تصمیمات بهینه بگیرد. نسبت رقابتی یک الگوریتم آنلاین ONL بدترین نسبت ممکن برای بازگشت OPT به بازگشت ONL ، نسبت به کلیه توالی های ورودی (قیمت) ممکن است. ماهیت چند برابر تعریف بازده (به جای مشخص کردن مقدار منفی برای از دست دادن) به این معنی است که در صورت از دست دادن ، نسبت رقابتی را می توان به روش عادی محاسبه کرد: به عنوان مثال ، اگر OPT بازگشت 2 را بدست آورد وONL بازگشت 1/3 ، سپس نسبت رقابتی 6 است.

سه مدل در مورد دانش الگوریتم آنلاین

We consider three different models on how the price changes, or equivalently, what knowledge the online algorithm has in advance. In the first model, the stock prices are always within a range [ m .. M ], i.e., m is the minimum possible price and M the maximum possible price. Both m and M are known to the online algorithm up front. In the second model, the prices still fluctuate within this range, but m and M are not (initially) known; instead only their ratio (varphi = M/m) , called the fluctuation ratio , is known. In both these models the length of the time horizon (number of days) is unknown (until the final day arrives). In the third model, called the bounded daily retu model , there is no global minimum or maximum price. Instead, the maximum fluctuation from day to day is bounded: namely, the price (p(i+1)) of the next day is bounded by the price p ( i ) of the current day by (p(i)/eta le p(i+1) le alpha p(i)) for some (alpha , eta >1 ). این بدان معنی است که قیمت ها نمی توانند ناگهان تغییر زیادی کنند. بسیاری از بازارهای سهام به اصطلاح "قطع کننده مدار" را اجرا می کنند که در هنگام رسیدن به چنین محدودیت هایی ، معاملات متوقف می شود. در اینجا ( alpha ، beta ) و مدت زمان تجارت t به الگوریتم آنلاین شناخته شده است. هر سه مدل در ادبیات الگوریتم به خوبی تثبیت شده اند. به عنوان مثال مراجعه کنید[1 ، 5].

نتایج قبلی و کارهای مرتبط

تجارت مالی و مشکلات مرتبط با آن کاملاً مباحث مهمی است و از دیدگاه الگوریتم های آنلاین بسیار مورد مطالعه قرار گرفته است. یک نظرسنجی جامع توسط Mohr et al.[10]در اینجا ما فقط برخی از نتایج مهمتر و مواردی که به مشکلاتی که در اینجا مطالعه می کنیم ، نمونه می گیریم. در مشکل جستجوی یک طرفه ، پخش کننده آنلاین یک لحظه از زمان را انتخاب می کند تا یک معامله واحد را از یک ارز به ارز دیگر انجام دهد. بازده آن به سادگی قیمتی است که معامله در آن انجام می شود. یک سیاست مبتنی بر قیمت رزرو (RP) خرید به محض رسیدن قیمت یا بالاتر از قیمت رزرو از پیش تعیین شده است. کاملاً مشهور است که ، اگر M و M شناخته شده باشد ، سیاست RP با قیمت رزرو ( sqrt ) بهینه است و به یک نسبت رقابتی ( sqrt ) می رسد. اگر فقط ( varphi ) شناخته شده باشد ، پس هیچ الگوریتم تعیین کننده نمی تواند به نسبت بهتر از ( varphi ) برسد. با این وجود ، با کمک تصادفی سازی ، ترکیبی تصادفی از RP های مختلف ، نسبت رقابتی (O ( log varphi) ) را نشان می دهد اگر ( varphi ) شناخته شده باشد. حتی اگر ( varphi ) مشخص نباشد ، یک نسبت رقابتی از (o ( log varphi cdot log ^( log varphi)) ) حاصل می شود. برای تمام نتایج فوق و بحث های بیشتر به [5] مراجعه کنید.

در مشکل معاملاتی یک طرفه ، هدف دوباره به حداکثر رساندن مبلغ نهایی در ارز دیگر است ، اما می تواند چندین معاملات وجود داشته باشد ، یعنی همه پول را نباید به یکباره معامله کرد.(این تمایز اصطلاحات بین جستجو و تجارت در [5] استفاده شد ، اما در [10] غیر پیشگیرانه نامیده می شد. تجارت راه در [5] داده شد. این نسبت رقابتی بهینه دارد. آنها همچنین بین الگوریتم های تجاری یک طرفه و الگوریتم های تصادفی برای جستجوی یک طرفه رابطه برقرار کردند. از آن زمان بسیاری از تغییرات جستجوی یک طرفه یا مشکلات تجاری یک طرفه مورد بررسی قرار گرفته است. برخی از نمونه ها شامل مدل بازگشت روزانه محدود [1 ، 14] ، جستجوی K Minima/Maxima به جای یک [9] ، مرزهای متغیر زمان [4] ، قیمت های بی حد و مرز [2] ، جستجو با پیچیدگی مشاوره [3] و غیرهبشر

با این حال ، آنچه در اینجا مطالعه می کنیم ، یک نسخه دو طرفه از مشکل معاملاتی غیرقابل تحمل ، پاورقی 1 است که بسیار کمتر مورد مطالعه قرار می گیرد. در اینجا بازیکن آنلاین ابتدا باید از یک ارز (بگویید پول نقد) به دیگری (سهام) ، امیدوارم با قیمت پایین تبدیل شود و سپس در مقطع بعدی از سهام به پول نقد تبدیل شود ، امیدوارم با قیمت بالایی. تمام سرمایه گذاری ها باید پس از پایان بازی یا قبل از بازی ، به اولین ارز تبدیل شوند. این مدل در جایی مرتبط است که سرمایه گذاران فقط به سودهای کوتاه مدت و سوداگرانه علاقه دارند. برای مدل هایی با M ، M یا شناخته شده ( varphi ) و با یک تجارت ، اشمیت و همکاران.[11] یک الگوریتم رقابتی ( varphi ) داد. از همان RP برای خرید و فروش استفاده می کند. اما الگوریتم کاری را که به هیچ وجه تجارت نمی کند در نظر بگیرید. واضح است که این نیز ( varphi ) است زیرا سود ONL 1 و سود OPT حداکثر ( varphi ) است (اگر قیمت از m به m می رود). تعدادی از استراتژی های تجاری مشترک ، مانند مواردی که بر اساس میانگین های متحرک انجام شده است ، در [10] مورد مطالعه قرار گرفت. نشان داده شد که آنها ( varphi ^2 ) هستن د-رقابتی (و بهتر نیستند) ، که به همین دلیل حتی بدتر هستند. به راحتی می توان نشان داد که این الگوریتم ها نسبت های رقابتی ( varphi ^k ) و ( varphi ^) دارند. شرودر و همکاران.[13] برخی از الگوریتم ها را برای مدل بازگشت روزانه محدود ، بدون محدودیت در تعداد معاملات ارائه داد. با این حال ، بسیاری از الگوریتم های فوق تمایل به تصمیم گیری هایی دارند که به وضوح بد هستند ، بدترین عملکرد ممکن را دارند (مانند از دست دادن بیشترین عامل ممکن هر روز در طول) ، و نسبت های رقابتی بهتر از آنچه توسط Do-Nothing داده می شود ، ندارند.

اخیراً اشمیت [12] همان مسئله دو طرفه غیرقابل انکار را در نظر گرفت ، اما با تعداد "اجرا" (دنباله ای از قیمت های یکنواخت افزایش یا کاهش) پارامتر می شود ، نه تعداد معاملات مجاز. به عبارت دیگر ، آنها تعداد حداکثر/حداقل محلی را محدود می کنند. Kao و Tate [8] همچنین نوعی مشکل "تجارت دو طرفه" را در نظر گرفتند ، اما چندین تفاوت اساسی با ما وجود دارد: (1) "قیمت" آنها از 1 به N رتبه بندی می شود.(2) "سود" هر تجارت تفاوت در رده ها است و هدف این است که حداکثر سود را به حداکثر برساند.(3) ورودی به ترتیب یکنواخت تصادفی است ، مانند مشکل دبیر.(4) آنها یا یک تجارت یا تعداد نامحدود معاملات را در نظر می گیرند.

سرانجام ، برای نسخه قابل تقسیم مشکل تجارت دو طرفه ، ال یانیو و همکاران.[5] بر اساس الگوریتم معاملات یک طرفه مبتنی بر تهدید آنها ، الگوریتمی را ارائه داد. نسبت رقابتی به دست آمده و همچنین مرز پایین آنها در تعداد بهینهای محلی دنباله قیمت نمایی است.

نتایج ما

در این مقاله ما مشکل معاملاتی دو طرفه را در نظر می گیریم که در آن یک شماره K محدودیت معاملات مجاز است و الگوریتم های بهینه را استخراج می کنیم. ابتدا مدل را با M و M شناخته شده در نظر می گیریم. ما با در نظر گرفتن مورد (k = 1 ) شروع می کنیم. اگرچه برخی از الگوریتم های ساده لوح شناخته شده اند که ( varphi ) هستن د-رقابتی و به نظر می رسد هیچ چیز بهتری امکان پذیر نیست ، اما ما از هیچ محدودی پایین تر آگاهی نداریم. ما یک مرز پایین تر از ( varphi ) می دهیم ، نشان می دهد که الگوریتم های ساده لوح نمی توانند بهبود یابند. نتیجه نیز در اثبات محدوده پایین بعدی مورد نیاز است.

شاید این باور داشته باشیم که هیچ چیز نمی تواند الگوریتم ساده لوح را نیز در مورد معاملات بیشتر شکست دهد. جالب اینجاست که ما ثابت می کنیم که برای (k ge 2 ) این درست نیست. در حالی که الگوریتم های ساده لوح مانند d o-nothing بهتر از ( varphi ^k ) نیستند ، ما نشان می دهیم که یک الگوریتم مبتنی بر قیمت رزرو ( varphi ^) رقابتی است. به عنوان مثال ، هنگامی که (k = 2 ) ، آن ( varphi ^) اس ت-به جای سه گانه ( varphi ^2 ) -رقابتی. علاوه بر این ، ما یک محدوده پایین تر را اثبات می کنیم ، نشان می دهد که الگوریتم بهینه است.

در مرحله بعد ، ما این مدل را در نظر می گیریم که فقط ( varphi ) شناخته شده است ، و یک الگوریتم با نسبت رقابتی ( varphi ^) ، یعنی فقط یک عامل ( varphi ^) بدتر از آن است. مدل قبلی که دانش بیشتری دارد. باز هم نشان می دهیم که این محدودیت بهینه است.

سرانجام ما مدل بازگشت روزانه محدود را در نظر می گیریم و دو الگوریتم بهینه ارائه می دهیم که در آن نسبت رقابتی به ( alpha ، beta ) و t بستگی دارد. به عنوان مثال ، با یک تجارت و در مورد متقارن ( alpha = beta ) ، نسبت رقابتی ( alpha ^) است. در حالی که این در T (که اجتناب ناپذیر است) نمایی است ، الگوریتم های ساده لوح می توانند هر روز به یک عامل ( max ( alpha ، beta) ) از دست بدهند ، و هیچ کاری نسبت به رقابتی ( alpha) ندارد.^t ). یکی از الگوریتم ها از استراتژی "توقف ضرر / قفل" استفاده می کند که معمولاً در تجارت واقعی استفاده می شود. تا آنجا که ما آگاه هستیم ، این اولین بار است که تجزیه و تحلیل رقابتی این استراتژی معاملات بازار سهام مشترک را توجیه می کند ، و در واقع نشان می دهد که حد از دست دادن توقف باید باشد. مواردی وجود داشت که تجزیه و تحلیل رقابتی استراتژی های سرمایه گذاری شناخته شده را به دست می آورد: ال یانیو و همکاران.[5] مشاهده کرد که الگوریتم آنها برای تجارت یک طرفه تقسیم شده ، هنگامی که بدترین دنباله قیمت ممکن است ، از خرد متعارف "میانگین هزینه دلار" پیروی می کند. با این حال ، در مدل بازگشت روزانه محدود ، میانگین هزینه دلار بهینه نیست [1].

M و M شناخته شده

در این بخش ، جایی که ما مدل را با M و M شناخته شده در نظر می گیریم ، می توانیم بدون از دست دادن کلیت فرض کنیم که (M = 1 ). همچنین به این معنی است که m و ( varphi ) برابر هستند و گاهی اوقات به صورت متناوب مورد استفاده قرار می گیرند. علاوه بر این ، ما توجه می کنیم که می توانیم بدون از دست دادن کلی بودن فرض کنیم که هر الگوریتمی با قیمت m خریداری نمی کند ، زیرا هر تجارت با چنین قیمت خرید فقط می تواند حداکثر 1 سود داشته باشد و حذف تجارت نمی تواند بازده کل را بدتر کند. به همین ترتیب نمی توانیم هیچ الگوریتمی را با قیمت m بفروشیم.

lemma 1

For any (epsilon >0 ) و هر الگوریتم آنلاین تعیین کننده ONL ، یک دنباله قیمت وجود دارد به طوری که OPT با یک عامل ( varphi ^) بازده ای بیشتر از ONL بدست می آورد. این امر حتی اگر ONL بتواند تعداد نامحدودی از معاملات را ایجاد کند و OPT فقط از یک تجارت استفاده کند ، صدق می کند.

اثبات

(n = lceil 1/ epsilon rceil ) را انتخاب کنید و (v_i = m^) را برای (i = 0 ، 1 ، ldots ، n ) تعریف کنید. توالی قیمت زیر تا زمان خرید ONL منتشر می شود:

اگر ONL در هیچ نقطه ای خریداری نکند ، بازگشت آن حداکثر 1 است. سپس Opt را در (V_1 ) خریداری می کند و در M می فروشد تا بازگرداندن (m^) دریافت کند. بنابراین فرض کنید onl برای برخی از (1 le i le n-1 ) در (v_i ) خریداری می کند.(نمی تواند در (V_0 ) بخرد زیرا روز گذشته است.) به محض خرید ONL ، بقیه دنباله منتشر نمی شود. در عوض قیمت به M کاهش می یابد و بازی به پایان می رسد. بازگشت ONL (m/v_i ) است. اگر (i = n-1 ) ، پس از آن تجارت نمی کند و بازگشت آن 1 است ، بنابراین نسبت بین بازده آنها (v_/m = m^) است. در غیر این صورت ، اگر (i ) (دو روز قبل از خرید ONL) و در روز بعد با قیمت m به فروش می رسد ، و بازگشت (m/v_ ) را باز می گرداند. بنابراین نسبت بین بازده آنها (mv_i/(mv_) = m^) است.

بنابراین در همه موارد ، نسبت بین بازده آنها حداقل (m ^ ge varphi ^ ) است.(مربع )

برای (k = 1 ) (هر دو OPT و ONL یک تجارت مجاز هستند) ، لمی فوق بلافاصله دلالت بر این دارد که هیچ الگوریتم قطعی بهتر از ( varphi ^) نیست. همچنین بدیهی است که الگوریتم کاری بدون هیچ چیز ( varphi ) -رقابت است ، بنابراین مرزها (تقریبا) محکم هستند.