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?
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