I haven’t posted anything for the last few weeks as I was busy with finals. Now that I’m (almost) done, I will have a lot more time on hand to do (and read!) interesting things which I can then write about.
This semester was my last at McGill and it feels a bit strange to think that I’m done with my undergrad. As I hadn’t done any elective courses over the previous three years, I had completed all my degree requirements but still had a few credits left over to do with as I pleased. I picked a few upper-year courses in Philosophy and Computer Science, and although I probably should’ve picked courses which would have been better for my GPA, I couldn’t turn these courses down.
The COMP course on algorithm design I have done this semester has been the most interesting computer science course I have done so far. It dealt with graph theory, network flows, and dynamic programming. To illustrate, here is a sample problem on network flows:
“As a response to natural disasters, we want an algorithm to assign ‘n’ injured people to k hospitals. There is an unlimited supply of ambulances, but everybody should be transported to a hospital within a 30 minute drive of their current location. Finally, in order to balance the load, every hospital should receive at most ‘n/k’ people. Describe a polynomial time algorithm to accept as input an ‘nxk’ array of driving times which will decide if a balanced assignment of people to hospitals is possible, and provide an assignment of each patient to each hospital.”
Network flow solutions and algorithms find particular application in matching problems (as the one above), so I’m thinking one application could be in Auction Theory or perhaps in market micro-structure design. I will have to read more into both these categories to see if and how network flow algorithms are applied. I also read a paper a while back which used network flow analysis to determine the spread of a liquidity crunch across financial institutions. Interesting stuff.
Dynamic programming was, for me, the most difficult to get my head around. Both network flow and dynamic programming problems remind me of the types of problems you would see in a math puzzle book, just made more formalized and mathematical. As an example, here is a dynamic programming problem:
“Consider a 2-D map with a horizontal river passing through its center. There are ‘n’ cities on the southern bank with x-coordinates a(1) … a(n) and ‘n’ cities on the northern bank with x-coordinates b(1) … b(n). You want to connect as many north-south pairs of cities as possible with bridges such that no two bridges cross. When connecting cities, you can only connect city ‘i’ on the northern bank to city ‘i’ on the southern bank. Write an algorithm which gives the best possible pairs of cities to connect such that no bridges overlap.”
The problems associated with both network flows and dynamic programming look deceptively simple. Once you start working on them you realize their complexity and after you have been working on them for a while, they become simple again. You begin to reduce new problems you encounter to old ones you’ve already seen and structure their solutions accordingly. For example, the one above can be reduced to something called the ‘Longest Integer Sequence’ problem and the solution can be obtained fairly easily after that.
Applications in finance? Glad you asked!
The key fact about dynamic programming is that it provides global solutions (as opposed to local solutions) for multi-variable decision making problems. This means that, unlike greedy algorithms, it doesn’t get stuck in local maximums. Thus we can be reasonably certain that the solution we obtain is the ‘best’ one.
One interesting paper I found is this one from Cornell, which explains the use of dynamic programming for portfolio optimization where the drift in market prices from state to state is modeled by an unobserved Markov chain. Information on the state of the Markov chain is obtained by both stock prices and signals at random discrete time points (which model ‘expert opinion’ in the market). These signals model expert opinion by helping gauge what the stock price will be by revealing the state of the Markov chain. Using dynamic programming, we can determine an optimal portfolio allocation under these conditions.
This is another paper from the International Journal of Business and Management .The problem here is kind of a simplified version of the one above. We basically have many asset classes with known returns across a known time period. Our problem is to determine the optimal allocations across the different time periods. This is more of a backward-facing problem and a purely theoretical exercise but useful nonetheless in understanding how dynamic programming could be applied to asset allocation.
I also found these slides very useful in understanding the application of dynamic programming to asset allocation, minimization of execution costs, and option pricing.