A website about the ZIP autonomous adaptive trading agent algorithm.For cool new stuff see: www.ziptrader.org/zip60
The rest of this page is unchanged from first imprint, September 2005
Why this is here: for several years, Dave Cliff, the inventor of the ZIP algorithm, maintained a web page (very much like this one) that was publicly available on the website of Hewlett-Packard Labs, where much of the early work on ZIP was done. When Dave resigned his job at HP in the spring of 2005, HP followed their usual practice of deleting all of his web material (and his email address) shortly after he left. The HP webpage on ZIP had been there for so long that some people had started referring to it (and citing it in academic papers) as if it was a permanent public archive, but it wasn't.
So, this site is intended to serve as an archive for the same chatty background material on ZIP, with pointers to some technical publications and some media coverage. All the content here (or pointed to from here) is in the public domain. Naturally, that means that some commercially sensitive material, such as the latest extensions and refinements of ZIP-based trading algorithms, are not mentioned here until they are protected by appropriate patent applications.
If you are looking for help with business applications of ZIP, need technical consultancy, or are wanting to license commercial use of the most recent (more powerful and more sophisticated) versions of ZIP, please talk to the nice folk at Syritta Algorithmics (www.syritta.com), who are the owners of this webpage. Syritta are a commercial operation: they're very friendly (and their lawyers are too, unless you annoy them), but they don't do things for free.
For details of some recent press/media coverage of this work, click here. For Dave Ciff's bio, click here.
The rest of this site is adapted/extended from the text written by Dave Cliff for his original ZIP Trader site at HP Labs...
This web-page gives an informal overview of relevant work on adaptive software agents that act as traders in electronic auction marketplaces such as the ones on which the international financial markets are based. There's some background material; then some brief notes on the "ZIP" trader algorithm that I invented in 1996, including a pointer to work published by IBM in 2001 which showed that ZIP traders can consistently out-perform human traders; and then a description of recent work in which a genetic algorithm is used to design new types of marketplace (i.e., new auction mechanisms) for the traders to interact within.
Why should you be interested? The IBM researchers claim that their results could herald the dawn of a new multi-billion-dollar industry: building artificial traders to replace humans (because the artificial traders are more efficient and more profitable than humans). If that is the case, then it turns out there is another multi-billion-dollar industry just waiting to happen...
...because, if you're going to eliminate the humans and populate your marketplaces with software agents, why should you use a style of marketplace designed by humans for humans? Why not try to design a marketplace that is better-suited to artificial agents?
Well, designing marketplaces is tricky, but it's now been demonstrated that a genetic algorithm (GA) can be used to explore an infinite space of new styles of auction for ZIP trading agents, and the GA can discover wholly new types of auction that are more efficient (more profitable) than existing human marketplace designs. These new auction styles are peculiar hybrids of existing designs: they are unlike anything ever designed by a human for a human, yet they are very easy to implement as online electronic auctions.
These results were presented at a conference in Hawaii on May 14th, 2002. That was the first time ever that a new electronic marketplace designed automatically (via a genetic algorithm) had been demonstrated to be more efficient than a human-designed market.
In absolute terms, the gains in efficiency/profitability are pretty small: a few percent or maybe a fraction of a percent. But with the trillions of dollars that flow through the current human-trader electronic auctions that make up the global financial markets, a gain of a fraction of a percent of those trillions of dollars can easily translates into a cash gain measured in millions of dollars. Potentially many millions of dollars. So there you go: these new results may herald the birth of another billion-dollar industry.
In the language of economics, the word "auction" is used to refer to the means by which buyers and sellers come together to exchange money for goods. There are lots of different types of auction.
One of the most famous types is the English Auction, where the seller stays silent and the buyers announce increasing bid-prices until only one buyer remains, who gets the deal. This is a popular way of selling fine art, and livestock too.
If you go to Amsterdam or Rotterdam and try to buy tulip bulbs (a big business in the Netherlands) you'll see almost exactly the opposite process in action. In the Dutch Flower Auction, the buyers stay silent while the seller starts with an initial high offer-price and then gradually drops the offer price until a buyer jumps in to take the deal.
By the way: when you're in a shopping mall, you're in an auction too. It's what an economist refers to as a Posted Offer Auction: the sellers name their offer-prices, and the buyers simply take it or leave it at that price.
But it hasn't always been that way. In pretty much all human societies for the last few thousand years, buyers and sellers meet at marketplaces and haggle: the seller states the offer-price, the buyer responds with a bid-price that is lower than the offer. The seller drops the offer a little; the buyer increases the bid a little; and they repeat these price revisions until they have struck a deal or one side gives up on the haggling and no deal occurs.
In fact, a close relative of this haggling process is the style of auction on which all of the world's major financial markets are based. This is sort of like having the English auction and the Dutch Flower auction going at the same time. It is known as the Continuous Double Auction, or CDA for short. In the CDA, a buyer can announce a bid at any time and a seller can announce an offer at any time. While this is happening, any seller can accept any buyer's bid at any time; and any buyer can accept any seller's offer at any time. Its a continuous asynchronous process, and it needs no centralised auctioneer.
The CDA interests economists because, even with a very small number of traders, the transaction prices (i.e. the agreed deal-prices) rapidly approach the theoretical market equilibrium price. The equilibrium price is the price that best matches the quantity demanded to the quantity supplied by the market, and in that sense it is the most efficient price for the market. The CDA is also of pragmatic interest because of the trillions of dollars that flow through national and international CDA-based markets in commodities, securities, capital, and derivatives.
"ZIP" stands for "Zero-Intelligence Plus". ZIP traders are minimally simple software agents with almost (but not actually) zero intelligence. I invented the ZIP algorithm in 1996, in response to pathological failures in Gode & Sunder's more famous "Zero Intelligence" (ZI) traders. For the full details see my technical report available at:
NB: this is a very long report (128 pages) which includes all the source-code for the program I wrote (in the C programming language) to demonstrate the failings in ZI traders and to show the lack of those failings in the ZIP traders. This paper also includes some introductory notes, for people unfamiliar with economics.
For readers with less time on their hands (or less space in their briefcases), that big report was broken into a series of much smaller self-contained papers, each addressing one issue of my work on ZIP traders. Most of these shorter papers refer back to the big HPL-97-91 report for more details. Here are some of them:
This paper: http://www.hpl.hp.com/techreports/97/HPL-97-157.html explains the problems with Gode & Sunder's ZI traders, in 6 pages.
This paper: http://www.hpl.hp.com/techreports/97/HPL-97-155.html explains how ZIP traders work, in 6 pages.
This paper: http://www.hpl.hp.com/techreports/98/HPL-98-17.html explains how ZIP traders can be used in a particular application area: Market-Based Control (MBC). In MBC, the metaphor of free-market economics is used to create distributed dynamic resource-allocation and control systems. Successful examples have been demonstrated in computer networks, in telecommunications applications, and in air-conditioning systems. This paper is 8 pages long.
These short papers were all co-authored with Janet Bruten, who made it possible for me to do this work at HP Labs by setting up and managing the "visiting academic" post that I held there in 1996, which is when I invented ZIP. Janet and I published a paper in the Adaptive Behavior journal too:
D. Cliff & J. Bruten (1999) "Animat Market-Trading Interactions as Collective Social Adaptive Behavior" Adaptive Behavior, 7(3/4):385-414. MIT Press.
The pre-publication draft is available here, for those of you who have trouble tracking down a copy of the final published journal article.
In the summer of 2001, an IBM research team demonstrated that ZIP trader agents consistently out-performed human traders in a series of human-vs.-agent experiments. (To do these experiments, they had to modify the ZIP algorithm slightly, but fundamentally the IBM implementation of ZIP traders uses the same adaptation/learning system as my original version). IBM have developed their own trader algorithm called MGD, which did no better than ZIP in the human-vs.-agent experiments they reported. For further details, see the paper by the IBM team, their web presentation of that paper, that team's homepage, or a nice New Scientist article. In their paper, the IBM team state that the financial impact of their results "...might be measured in billions of dollars annually."
What the IBM team didn't know at the time they were doing their experiments is that since 1997 I'd been working on using artificial evolution to improve the performance of ZIP traders. I'd used a straightforward genetic algorithm (GA) to tailor the ZIP control parameters to particular markets. I'd started this work while I was at the MIT AI Lab, and then continued it when I left MIT to join HP Labs. Some very early results from this GA-ZIP work had been presented at a financial engineering conference in New York in spring 1998, and some more solid results at a software-agent workshop in Minneapolis a couple of months later, but for various reasons the paper covering those two presentations wasn't actually published until 2001. It is available here:
I suspect that if the IBM team had used my GA method before unleashing the ZIPs on the humans, the ZIPs would have done even better in their experiments.
Evolving Auction Mechanisms
The wonderful results in the IBM paper, and the success of using the GA to get better ZIPs, led me to think about using a GA to design new marketplaces that are specialised for trading agents. First results from this work were presented at a financial engineering special session at the WCCI conference in Hawaii on May 14th, 2002. The Hawaii paper is available from here:
The results in the Hawaii paper were superseded by a further set of GA-ZIP results, in a paper presented at the Agents for Business Automation (ABA02) conference in Las Vegas in June 2002. These new results showed that, to be robust to sudden sharp changes in supply or demand, two-sided auctions (where neither the buyers nor the sellers stay entirely silent) are more likely to evolve than one-sided auctions such as the English or Dutch Flower auction. The Las Vegas paper is available from here:
Both these evolving-auction papers demonstrate that it is possible for the GA to find new "hybrid" designs of auction mechanism that are demonstrably better than the human-designed English Auction, Dutch Flower Auction, and CDA mechanisms. The evolved auctions are "better" in the sense that transaction prices tend to be closer to the theoretical equilibrium price in the evolved hybrid auctions than in the non-evolved human-designed mechanisms. As far as I know, these two papers were the first time anyone had ever published results from evolving the market mechanism while also evolving the traders. New Scientist wrote a news item on this research (23rd May 2002) and BBC Radio 4's Material World ran a 12-minute feature on it (22nd August 2002).
Coincidentally, a project with similar aims but different methods had recently started at the University of Liverpool, UK. Their first results were presented a couple of months after mine, at a workshop in New York City in July 2002.
Over the summer of 2002, three postgraduate students each working for their masters thesis investigated aspects of this work:
Zengchang Qin at the University of Bristol wrote a thesis describing his replication of my original evolving-market experiments and then explored some alterations (including one that allowed proper instances of the one-sided English and Dutch auctions to evolve.) Zengchang's homepage is here.
Neil Robinson from the University of Sussex wrote a thesis where he also replicated my original GA-ZIP results and then applied these new techniques to evolve ZIP-trader auction mechanisms for market-based control of large compute facilities. Neil's thesis (242 pages) is available as an HP Labs technical report from here:
Vibhu Walia from the University of Birmingham wrote a thesis where he described the discovery of qualitatively similar results (i.e. evolved hybrid auction mechanisms giving optimal performance) in e-marketplaces populated by another form of simple trading agent: Gode & Sunder's "ZI" traders. Vibhu's thesis (106 pages) is available as an HP Labs Technical Report from here:
Vibhu co-authored a couple of 8-page papers with me and my HP Labs colleague Dr Andrew Byde. The first of these is accepted for presentation at the 2003 International Conference on Computational Intelligence for Financial Engineering (CIFEr03), Hong Kong, March 2003, and is available here:
The second paper by Vibhu, Andrew, and me is available here:
Following this, I wrote a paper on visualising the fitness landscapes that underlie the ZIP-trader evolving-mechanism problems. That paper was presented at a workshop at the AlifeVIII conference in Sydney in December 2002. A very heavily abridged copy (with many figures omitted) was circulated at the workshop, but the full version with all figures is available from here:
Also over the summer of 2002, my colleague Dr Andrew Byde used similar techniques (i.e., a GA) to evolve new forms of hybrid sealed-bid auction mechanisms. Again, these evolved hybrid mechanisms were found to outperform the traditional non-hybrid human-designed forms. Andrew has written a paper on this work, available from here:
My work on evolving auction markets was the subject of an article in the Finance & Economics section of the November 28th 2002 edition of The Economist, and a copy of that article is available here for subscribers. This sparked a lot of interest from the global financial industry, both from professional traders and from people who run national exchanges.
In summer 2003 I had a paper published in the Journal of Electronic Commerce Research and Applications (published by Elsevier) which started out as an expanded version of the 2002 Las Vegas paper, but ended up as a fairly exhaustive empirical exploration of the effects that shock-changes to the market supply and demand curves have on the resulting evolved market mechanisms. A near-final draft is available as an HP Labs technical report from here:
And the final published version of the paper can be downloaded from here:
Cliff. "Explorations in evolutionary design of online auction market
Not much has been published since then, mainly because we were working on some commercially sensitive applications and extensions, and we got side-tracked into making some money too.
There's a new paper coming out soon that will talk about how to make ZIP even better, along with a fresh release of the revised source code, to show exactly how it's done.
Please remember that this research theme is ongoing. There are many aspects of these results that remain to be explored and there are also some significant research issues that would need to be overcome before these results could be robustly applied to real-world markets. More results from our research into automated market-mechanism design will be published in due course, and this web page will be updated accordingly.
Copyright © 2001-2005, Dave Cliff.