Multi-Agent Algorithms
I’m currently doing some work on Mutli-Agent Algorithms for a company in the UK and I thought it might make a nice topic for a post.
A multi-agent algorithm is an algorithm that attempts to simulate a complex phenomenon and thereby solve or make useful predictions and strategies for the phenomenon using millions of simulated autonomous agents.
For example, consider the stock market. The price of each individual stock may seem quite random when viewed on a large scale. However, upon further inspection we can see that the current price of a stock is the result of thousands of interactions over time between a set of traders. Each trader brings his knowledge, his expectations and his goals to the trading floor causing small shifts in price.
In reality the stock market shouldn’t be seen as a mysterious set of trends and price lines. It should be viewed more like an enormous Ebay auction with millions of bidders buying and reselling the items everyday.
The Multi-Agent algorithm’s main advantage then is that they allow a back door type of simulation of phenomenon that are too complex to model directly and they can do it in fractions of the time required for the real phenomenon upon which they are based.
From this “back door” simulation it is possible to derive rules for maximizing some function. For instance, if we simulate the stock market in such a way as to mimic the real stock market, we can monitor the agents who seem to be making good profit with their trading activities and derive trading schemes based on their characteristics. We can then apply those trading schemes to real stock trading.
A Basic Pseudo Algorithm for a Multi-Agent Model is:
-Initialize agents with a description of their bidding strategies
-Initilize marketplace by defining rules for trading the goods
-Step through time allowing each agent to make bids for the objects in the marketplace according to his bidding strategy
-Record new price data, step forward
-Repeat bidding, selling and final pricing steps until a meaningful amount of time has passed
-Select most desirable agents, analyze them and let them reproduce and evolve if desired
For further reference try this site…very interesting.
Related posts:
September 17th, 2008 at 9:45 pm
Speaking of simply-complex systems… fractal generation is based on exactly this concept, as are the myriads of random-action toys (usually 2 or 3 interacting non-linear motions). I coded a Mandelbrot set generator for a Commodore 64 in the way-back times. There were 300 lines of basic code to initialize variables, peak and poke things into memory and reconfiguring to poke into video memory… then there was the algorithm code… one, very short line. You just take a complex number c(1) = ( ix+y), then iterate: c(n+1) = c(n)^2+c(1), then repeat. If it’s distance from 0,0 gets bigger than 1 (or some other chosen boundary), it is not in the set. If it doesn’t it is in the set. From that little formula you get all of the complexity of the Mandelbrot set!
Lorentz (I worked with his daughter at Quest!) said that the weather was fractal… well, he didn’t have that word… he said that the system was infinatesimally complex with just a few variables… After trying to predict the weather with a building size “super computer” he said that if he had as big and fast a computer as he wanted, and had air temp, pressure, velocity, and humidity at the vertex of every cubic foot of the atmosphere, he could not predict the weather!!! The tiniest change in any initial condition led to radically different output — The butterfly effect indeed!!
Check it out:
http://www.math.utah.edu/~pa/math/mandelbrot/mandelbrot.html