Wednesday 28 July 2010

Stop the Traffic

Traffic flow is a strange phenomenon. The complex interaction of drivers results in strange emergent behaviour, such as snarled up traffic even in what seem like ideal driving conditions.

A microsimulation is a modelling technique that models individual units. Microsimulations are used for a number of items, including health sciences, pedestian modeling and traffic simulation.

My simple traffic microsimulation is based on a simple car-following model. If there's nothing nearby, drivers keep a constant speed. Seeing a car ahead, drivers have the irresitable urge to catch up with them, and thus put their foot down. Seeing a car ahead that's a little too close, drivers slam their brakes on. Overtaking is strictly prohibited! This is a deliberately simple model, just to see if the behaviour emerges; there's a number of much sophisticated models available such as Gipps' or Intelligent Driver Model.

The simplest model I could think of is a giant round-about. Cars circle the roundabout as fast as possible, assuming the basic model described above. This results in a nice traffic shockwave much like the one shown in the video below.

The main data types are shown below and are (hopefully?) self-explanatory. Rather than store the position of a car directly, I just store the distance to destination. This makes placing the car and determing the distance between them considerably simpler. I've used an infinite list of randomness to provide a source of noise to the simulation.

The actual logic of the simulation is equally simple. All we have to do is reposition the cars based on their speed. I've made lots of simplifying assumptions. For example, I'm only considering cars on the same route as being near and I'm not allowing cars to overtake.

Putting this together with some OpenGL code gives the following.

The full code for this is on my GitHub page and (as always!) any suggestions on how to improve the code are greatly received! I have a sneaking suspicion I should be using a State monad somewhere in here, but it's not quite clicked how yet!

(edit 3rd August 2010)

I updated the code in the gist with the corrections that Edward Kmett kindly provide. Much better looking results now, though my screen capturing skills still lead a little to be desired. If you download the code you can now change the speed / number of cars interactively and see what happens.

Thursday 15 July 2010

Foreign Exchange Arbitrage

Arbitrage exploits a price difference between two or more markets to make money with zero risk.

Sporting bets are perhaps the easiest example. Given a sporting event with two possible outcomes you look for an opportunity where two book makers give slightly different odds and try to expoit it. For example, consider a case with two outcomes, say Federer vs. Nadal. One bookie offers odds of 5/2 on Federer, whereas another offers odds of 3/5 on Nadal. If I bet £32 on 5/2, and £68 at 3/5 then regardless of the outcome I'm guaranteed to make a little money (a minimum of 8% in this case. £32 at 5/2 odds gives me $112 and £68 at 3/5 gives me £108). Wikipedia's page on arbitrage betting explains it better than I can!

Foreign exchange (forex) markets are another opportunity for the arbitrageur. By finding mispriced currencies you can get money for nothing. For example I could transfer my money from GBP to USD via CHF and end up with a profit if someone got these exchange rates wrong! Now all I need to do is find a way of finding these opportunities and I'll be rich!

The exchange rates can be represented as a weighted graph with each node representing a currency and each directed edge representing the exchange rate. To find an arbitrage opportunity we need to find a path through the graph (starting and ending at the same node) where the product of edge weights is greater than 1.0. The shortest path is the best one, because we want to make as few trades as possible. The Floyd Warshall algorithm is an efficient algorithm for finding the shortest paths in a weighted graph.

In the graph below we can make a trade 1 -> 2 -> 4 -> 3 -> 1 and make a profit.

Floyd Warshall is an example of dynamic programming. A dynamic programming solution has three components (from The Algorithm Design Manual):

  1. A recurrence relation or recursive algorithm for expressing the answer
  2. Show that the recursive version is bounded by a small polynomial
  3. An order of evaluation for the reccurence that means you always have partial results available when you need them.

We can define the arbitrage problem recursively. First we label the nodes as being number from 1 to N. The shortestPath(i,j,k) gives the shortest path from i to j using only nodes 1 to k as intermediate nodes. The base case is shortestPath(i,j,0) where the value is simply the edge weight between i and j. The recursive relation is shortestPath(i,j,k) = min(shortestPath(i,j,k-1), shortestPath(i,k,k-1) + shortestPath(k,j,k-1). The recurrence relation just says that each new node that we consider only helps if there is a shortest path that goes through it.

In order to code this up in Haskell we'll need some representation of a graph. A graph is simply a collection of vertices and some edges. In order to make things easier I've said that each vertice should be an enum and have an integer representation.

I've needed two language extensions (multi parameter type classes and functional dependencies) which seems overkill! Functional dependencies is used in Graph a b | a -> b to state that b is uniquely defined by a. Any suggestions on the simpler solution would be greatly appreciated!

Dynamic programming solutions can be expressed very neatly in lazy functional programming languages like Haskell. See here for more information, but the basic idea is to define a data structure in terms of itself. If we initialize the data structure in the correct order, then all the previous results are available when they are needed. This makes for a concise solution to the problem.

The Floyd Warshall algorithm has been extended a little above to find the minimum solution and to provide path reconstruction information. Once we have the path reconstruction matrix we can work backwards to reconstruct the series of trades that lead to an arbitrage opportunity. There's only an opportunity if there is a loop from a starting currency that returns with a value greater than 1.

So, I've now got the ability to find an arbitrage path if one exists, now all I need to do is hook my computer up to a live feed of exchange rates, put a little money in and I'll be rich by the end of the day. Just in case it's not quite that easy, I thought I'd better run it on some test data!

There's a good source of test data at GAIN Capital that's available here. I downloaded January's historial data and after a while ended up with 1.3GB of data to sort though. The data is in a simple CSV format, with columns representing the ticket, currencies, data time, bid rate and ask rate. This gave me an opportunity to use Parsec which is apparently an industrial strength, monadic parser combinator library. Thanks to RWH Chapter 16 it was pretty simple to use and understand.

Now that I've got a way of reading in the historical data in, I simply need to convert this data into a form that the Floyd Warshall algorithm can use and look for paths that give a profit. I could have done that directly with the parser code, but I might want to reuse that again for some other cunning plan. Instead I'll convert to a simple map representation, with the keys being pairs of vertices and the values being the exchange rate between those values. The following code takes a list of foreign exchange records, converts them into exchanges and looks for arbitrage opportunities.

Assuming that I've understood the format properly (anyone know any good books to get this kind of basic information?), then running this code through the 21 million (!) ticker updates in January 2010 yields absolutely ZERO arbitrage opportunities. With my limited knowledge, I think this is because of the efficient-market hypothesis. Prices reflect the information available and the updates are incredibly quick (otherwise currency traders would be going bankrupt on a daily basis!).

Back to the drawing board with my money making schemes!

(image taken from Flickr)