Competitive algorithms for unbounded one-way trading

In the one-way trading problem, a seller has L units of product to be sold to a sequence σ   of buyers u1,u2,…,uσu1,u2,…,uσ arriving online and he needs to decide, for each uiui, the amount of product to be sold to uiui at the then-prevailing market price pipi. The objective is to maximize the seller's revenue. We note that all previous algorithms for the problem need to impose some artificial upper bound M and lower bound m on the market prices, and the seller needs to know either the values of M and m  , or their ratio M/mM/m, at the outset.This paper gives a one-way trading algorithm that does not impose any bounds on market prices and whose performance guarantee depends directly on the input. In particular, we give a class of one-way trading algorithms such that for any positive integer h and any positive number ϵ  , we have an algorithm Ah,ϵAh,ϵ that has competitive ratio O(log⁡r⁎(log(2)⁡r⁎)…(log(h−1)⁡r⁎)(log(h)⁡r⁎)1+ϵ)O(log⁡r⁎(log(2)⁡r⁎)…(log(h−1)⁡r⁎)(log(h)⁡r⁎)1+ϵ) if the value of r⁎=p⁎/p1r⁎=p⁎/p1, the ratio of the highest market price p⁎=maxi⁡pip⁎=maxi⁡pi and the first price p1p1, is large and satisfies log(h)⁡r⁎>1log(h)⁡r⁎>1, where log(i)⁡xlog(i)⁡x denotes the application of the logarithm function i times to x  ; otherwise, Ah,ϵAh,ϵ has a constant competitive ratio ΓhΓh. We also show that our algorithms are near optimal by showing that given any positive integer h and any one-way trading algorithm A, we can construct a sequence of buyers σ   with log(h)⁡r⁎>1log(h)⁡r⁎>1 such that the ratio between the optimal revenue and the revenue obtained by A   is Ω(log⁡r⁎(log(2)⁡r⁎)…(log(h−1)⁡r⁎)(log(h)⁡r⁎))Ω(log⁡r⁎(log(2)⁡r⁎)…(log(h−1)⁡r⁎)(log(h)⁡r⁎)). A special case of the one-way trading is also studied, in which the L units of product are comprised of L items, each of which must be sold atomically (or equivalently, the amount of product sold to each buyer must be an integer).Furthermore, a complementary problem to the one-way trading problem, say, the one-way buying problem, is studied in this paper. In the one-way buying problem, a buyer wants to purchase one unit of product through a sequence of n   sellers v1,v2,…,vnv1,v2,…,vn arriving online, and she needs to decide the fraction to purchase from each vivi at the then-prevailing market price pipi. Her objective is to minimize the cost. The optimal competitive algorithms whose performance guarantees depend only on the lowest market price p⁎=mini⁡pip⁎=mini⁡pi, and one of M and φ, the price fluctuation ratio, are presented.