Buying in Rocket Ships and Selling in Fire Sale
Source: Asked to me by Ankush Jain (CSE IITB 2011, Morgan Stanley Quant Associate). He took it from Algorithms Design book by Tardos and Kleinberg
Problem:
Easy case:
You’re trying to buy equipments whose costs are appreciating. Item i appreciates at a rate of r_i > 1 per month, starting from $100, so if you buy it t months from now you will pay 100*((r_i)^t). If
you can only buy one item per month, what is the optimal order in which to buy them?
Difficult case:
You’re trying to sell equipments whose costs are depreciating. Item i depreciates at a rate of r_i < 1 per month, starting from $100, so if you sell it t months from now you will get 100*((r_i)^t). If
you can only sell one item per month, what is the optimal order in which to sell them?
Solution:
Highlight the part between the * symbols for the answer.
* Buying (appreciating, r_i > 1): buy in DECREASING order of r_i. Exchange argument: if you buy item with rate r at month t and item with rate s < r later at month u > t, swapping them changes the cost by (r^u + s^t) - (r^t + s^u) = r^t(r^(u-t) - 1) - s^t(s^(u-t) - 1) > 0 - the swap is strictly cheaper. So any inversion can be improved, and the sorted order is optimal. (Verified exhaustively on random instances.)
Selling (depreciating, r_i < 1): there is NO simple sorted-order rule - this is what makes the case difficult. The same exchange calculation gives, for adjacent items at months t and t+1 with rates r then s, that swapping helps iff r^t(1 - r) vs s^t(1 - s) compare the right way, and f(x) = x^t(1 - x) is not monotone in x (it peaks at x = t/(t+1)) - so locally better orders need not be globally sorted. Concrete counterexample to "sell slowest-depreciating last / sorted by r": rates {0.31, 0.38, 0.47, 0.82}. Sorted ascending gives 1 + 0.38 + 0.47^2 + 0.82^3 = 2.152, but the order (0.31, 0.47, 0.82, 0.38) gives 1 + 0.47 + 0.82^2 + 0.38^3 = 2.197 - strictly better. Exhaustive search on random 4-5 item instances finds non-sorted optima about a quarter of the time. The exact answer requires search: subset DP in O(n^2 * 2^n) (dp[S] = best revenue from set S sold in the first |S| months), or brute force for small n. Greedy heuristics like "sell the biggest absolute depreciator next" also fail in general.
(solution posted by AI - the comments had the buying case mostly right via the "grid" intuition, but the selling case was left open/contested; the counterexample above is computed, not copied) *
Are all items priced at $100? If they are, what's wrong with buying (and selling) the one with highest r_i first (and then in order of decreasing r_i)?
ReplyDeletePut more formally, considering n items, I would use a grid:
1,(1+r1),(1+r1)^2,.....(1+r1)^n-1
.
.
1,(1+rn),(1+rn)^2,.....(1+rn)^n-1
The question is now to select one no. from each row and column to minimise the sum. It can be proven that this happens when you select in order of decreasing r_i.
I feel like I'm missing something big here.. What part of above is incorrect?
it is correct, it is a greedy solution. the solution is simple, i think it is the correctness proof that requires some clever arguments
DeleteFor the selling case, consider the following rates( in absolute terms ) :
Delete99, 99, 1, 0.5
If you sell them in order of decreasing rates, you will get the following returns :
100/(1) + 100/(100) + 100/(2*2) + 100/(1.5*1.5*1.5 ) = 155.63
This is not the best selling sequence. A better sequence is : ( 99, 1, 0.5, 99 )
100/(1) + 100/(2) + 100/(1.5*1.5) + 100/(100*100*100 ) = 194.44
For the selling case, I think, we'd need to select in the order of increasing r_i. Since, we're trying to maximise the sum in that case. Correct?
ReplyDeleteHow to solve the second part apart from an exponential method
ReplyDeletejust a thought, is there an optimized way, even if initial prices of items differ ? like p,q,r,...instead of all being 100. i guess we should seek the sum of the entire column instead of just looking for r_i
ReplyDeleteFor selling:
ReplyDeleteI think we should calculate decrease in price at each time step for each remaining item and sell the one which might depreciate the most in value if we do not sell it immediately. This way we are greedily minimizing the total loss incurred.
Proof doesn't seem to be obvious, but it works on toy cases I constructed. Has anyone proved this or has a link to a solution?
what happens if the cost of each of the items are different ??
ReplyDeleteMy hypothesis is that we can, while buying, make a grid similar to what has been suggested by John and buy the most expensive item each month, deleting that row and column every month. In the limiting case of all items costing the same, the solution reduces to that of John.
what happens if the cost of each of the items are different ??
ReplyDeleteMy hypothesis is that we can, while buying, make a grid similar to what has been suggested by John and buy the most expensive item each month, deleting that row and column every month. In the limiting case of all items costing the same, the solution reduces to that of John.
I think in both case answer is decreasing order.
ReplyDelete