BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Computer Science and Engineering
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20250508T140000
DTEND;TZID=Asia/Kolkata:20250508T150000
DTSTAMP:20260924T034206
CREATED:20250507T062717Z
LAST-MODIFIED:20250507T063432Z
UID:1581-1746712800-1746716400@homecse.iitd.ac.in
SUMMARY:Trading Prophets: How to trade multiple stocks optimally
DESCRIPTION:Speaker: Surbhi Rajput\, MSR Student\, CSE Dept.\, IIT Delhi \nAbstract:\n\nIn the (single stock) \emph{trading prophet} problem formulated by Correa et\nal.\ [2023]\, an online algorithm observes a sequence of prices of a stock.\nAt each step\, the algorithm can either buy the stock by paying the current\nprice if it doesn't already hold the stock\, or it can sell the currently\nheld stock and collect the current price as a reward. The goal of the\nalgorithm is to maximize its overall profit. Correa et al.\ showed that the\noptimal competitive ratio for this problem is $\nicefrac{1}{2}$ when the\nstock prices are identically and independently distributed.\nIn this talk\, I will discuss the simplifications and generalizations of\nCorrea et al.'s analysis\, which led us to generalize the model by allowing\nthe algorithm to trade multiple stocks. First\, we generalize the model to\n$(k\,\ell\, \ell')$-\textsc{Trading Prophet Problem}\, wherein there are $k$\nstocks in the market\, and the online algorithm can hold up to $\ell$ stocks\nat any time\, where $\ell \leq k$. The online algorithm competes against an\noffline algorithm that can hold at most $\ell' \leq \ell$ stocks at any\ntime. Under the assumption that prices of different stocks are independent\,\nwe show that\, for any $\ell$\, $\ell'$\, and $k$\, the optimal competitive\nratio of $(k\,\ell\, \ell')$-\textsc{Trading Prophet Problem} is\n$\min\left\{\frac{1}{2}\,\frac{\ell}{k}\right\}$.\nWe further generalize it to $\mathcal{M}$-\textsc{Trading Prophet Problem}\nover a matroid $\mathcal{M}$ on the set of $k$ stocks\, wherein the stock\nprices at any given time are possibly correlated (but are independent across\ntime). The algorithm is allowed to hold only a feasible subset of stocks at\nany time. We prove a tight bound of $\frac{1}{1+d}$ on the competitive ratio\nof the $\mathcal{M}$-\textsc{Trading Prophet Problem}\, where $d$ is the\n\textit{density} of the matroid.\nWe then consider the non-i.i.d.\ random order setting over a matroid\,\nwherein stock prices drawn independently from $n$ potentially different\ndistributions are presented in a uniformly random order. In this setting\, we\nachieve a competitive ratio of at least $\frac{1}{1+d} - \mathcal{O}\n\left(\frac{1}{n} \right)$\, where $d$ is the density of the matroid\,\nmatching the hardness result for i.i.d.\ instances as $n$ approaches\n$\infty$.\nOur analysis of the above problems is based on the following key insights.\nFirst\, any algorithm can be simulated by one that\, on each time step\, sells\n\emph{all} its currently held stocks before buying a suitable subset of\nstocks. Second\, we prove that the general problem reduces to a restriction\nwhere the expected price of every stock is zero.\nThird\, we reduce the problem in the random order non-i.i.d.\ setting to the\ni.i.d. setting by leveraging the fact that the outcome of sampling two\nobjects without replacement from a large set is almost identically\ndistributed as the outcome of sampling with replacement.
URL:https://homecse.iitd.ac.in/event/trading-prophets-how-to-trade-multiple-stocks-optimally/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
CATEGORIES:Seminars
END:VEVENT
END:VCALENDAR