اکتشافات در طراحی تکاملی مکانیسم های بازار مزایده آنلاین

This paper describes the use of a genetic algorithm (GA) to find optimal parameter-values for trading agents that operate in virtual online auction ‘e-marketplaces’, where the rules of those marketplaces are also under simultaneous control of the GA. The aim is to use the GA to automatically design new mechanisms for agent-based e-marketplaces that are more efficient than online markets designed by (or populated by) humans. The space of possible auction-types explored by the GA includes the continuous double auction (CDA) mechanism (as used in most of the world’s financial exchanges), and also two purely one-sided mechanisms. Surprisingly, the GA did not always settle on the CDA as an optimum. Instead, novel hybrid auction mechanisms were evolved, which are unlike any existing market mechanisms. In this paper we show that, when the market supply and demand schedules undergo sudden ‘shock’ changes partway through the evaluation process, two-sided hybrid market mechanisms can evolve which may be unlike any human-designed auction and yet may also be significantly more efficient than any human designed market mechanism.

For thousands of years, buyers and sellers have come together to exchange money for goods or services. Economists use the word ‘auction’ to refer to the mechanism (or rules) by which buyers and sellers interact in such marketplaces. Almost all traders in the global international financial markets interact via a particular form of auction market mechanism known as the continuous double auction (CDA), more details of which will be given later. 1 The CDA has been the subject of much study by economists, partially because it is so important in the world of finance, but also because CDA markets typically exhibit a very attractive characteristic: experimental studies have demonstrated that the transaction prices in a CDA market rapidly converge on the market’s theoretical equilibrium price. Students of microeconomics know the equilibrium price as the price at which the market’s supply and demand curves intersect; but, colloquially, the equilibrium price is important because if transactions are taking place at off-equilibrium prices then someone somewhere in the market is being ripped off. Hence, rapid equilibration is desirable in any auction. The precise reasons why CDA markets typically exhibit rapid and stable equilibration are still the topic of research and debate (see e.g. Ref. [12]). With the advent of e-commerce, various forms of auction mechanism have become very popular for online trading, and web-based auction sites such as www.ebay.com have proven highly successful. As auctions dematerialize, moving online and becoming virtual ‘e-marketplaces’, it becomes perfectly plausible for software-agent ‘robot’ traders to participate in those auctions. In comparison to human traders, such ‘bots’ have the advantage of being very fast and very cheap, and in principle they can assimilate and act on volumes of data that would swamp even the most able of human traders. ZIP (zero-intelligence-plus) artificial trading agents, introduced in Ref. [3], are software-agent ‘trader bots’ that use simple machine learning techniques to adapt to operating as buyers or sellers in open-outcry auction-market environments similar to those used in Smith’s [22] pioneering experimental economics studies of the CDA and other auction mechanisms. ZIP traders were originally developed as a solution to the pathological failures of Gode and Sunder’s [13] ‘ZI’ (zero-intelligence) traders, but recent work at IBM by Das et al. [11] has shown that ZIP traders (unlike ZI traders) consistently out-perform human traders in human-against-robot experimental economics CDA marketplaces. The ZIP traders consistently made profits a few percentage points higher than did the human traders they were competing against. Das et al. [11] wrote that the ‘…successful demonstration of machine superiority in the CDA … could have a … powerful financial impact—one that might be measured in billions of dollars annually’, and in their conclusions they speculate on the future possibility of online e-marketplaces currently populated by human traders becoming populated entirely by trader agents. The operation of ZIP traders has been successfully demonstrated in experimental versions of CDA markets similar to those found in the international financial markets for commodities, equities, capital, and derivatives; and in posted-offer auction markets similar to those seen in domestic high-street retail outlets [3]. In any such market, there are a number of numeric parameters that govern the adaptation and trading processes of the ZIP traders. In the original 1997 version of ZIP traders, the values of these were set by hand, using ‘educated guesses’. However, subsequent papers [4] and [5] presented the first results from using a standard technique to automatically optimize these parameter values, thereby eliminating the need for skilled human input in deciding the values. Prior to the research described in Ref. [6], in all previous work using artificial trading agents—ZIP or otherwise—the market mechanism (i.e. the type of auction the agents are interacting within) had been fixed in advance. Well-known market mechanisms from human economic affairs include: the English auction (where sellers stay silent and buyers quote increasing bid-prices), the Dutch Flower auction (where buyers stay silent and sellers quote decreasing offer-prices); the Vickery or second-price sealed-bid auction (where sealed bids are submitted by buyers, and the highest bidder is allowed to buy, but at the price of the second-highest bid: game-theoretic analysis demonstrates that this mechanism encourages honesty and is robust to attack by dishonest means); and the CDA (where sellers announce decreasing offer prices while simultaneously and asynchronously the buyers announce increasing bid prices, with the sellers being free to accept any buyer’s bid at any time and the buyers being free to accept any seller’s offer at any time, in the absence of an auctioneer). In this paper, we explore in detail the some specific consequences of asking the following question: if, as Das et al. [11] speculate, trader agents will come to replace human traders in online e-marketplaces, then why should those online e-marketplaces use auction mechanisms designed by humans, for humans? Perhaps there are new market mechanisms, suitable only to populations of robot-traders, that are more efficient (or otherwise more attractive) than currently known human-based mechanisms. Designing new market mechanisms is hard, and the space of possible mechanisms is vast. For this reason it is attractive to use an automated search of the space of possible mechanisms: in essence, we ask a computer to do the auction-design for us. This paper reports on exploring the application of one type of automated search/optimization algorithm, which is inspired by Darwinian notions of evolution via random variation and directed selection, and hence is known as a genetic algorithm (GA). The first results from experiments where a GA optimizes not only the parameter values for the ZIP trading agents, but also the style of market mechanism in which those traders operate, were presented in Ref. [6]. To do this, a space of possible market mechanisms was created for evolutionary exploration. The space includes the CDA and also one-sided auctions similar (but not actually identical to) the English Auction (EA) and the Dutch Flower Auction (DFA). Significantly, this space is continuously variable, allowing for any of an infinite number of peculiar hybrids of these auction types to be evolved, which have no known correlate in naturally occurring (i.e. human-designed) market mechanisms. While there is nothing to prevent the GA from settling on solutions that correspond to the known CDA auction type or the EA-like and DFA-like one-sided mechanisms, it was found that hybrid solutions can lead to the most desirable market dynamics. Although the hybrid market mechanisms could easily be implemented in online electronic marketplaces, they have not been designed by humans: rather they are the product of an automated search through a continuous space of possible auction-types. Thus, the results in Ref. [6] were the first demonstration that radically new market mechanisms for artificial traders may be designed by automatic means. This is not a trivial academic point: although the efficiency of the evolved market mechanisms are typically only a few percentage points (or even only a few basis points) better than those of the established human-designed mechanisms, the economic consequences could be highly significant. According to figures released by the New York Stock Exchange (NYSE), the total value of trades on the CDA-based NYSE for the year 2000 was $11060 billion (i.e. a little over 11 trillion dollars: see [16]). If only 0.1% of that liquidity could be eliminated or captured by a more efficient evolved market mechanism, the value saved (or profit generated) would still be in excess of $10bn. And that is just for one market: similar savings could presumably made at NASDAQ, at European exchanges such as LSE and LIFFE, and at similar exchanges elsewhere around the globe. Section 2 gives an overview of ZIP traders and of the experimental methods used, including a description of the continuously variable space of auction types. This description is largely identical to the account given in previous papers [6] and [7], albeit extended to describe how the new experiments whose results are presented here differ from the previous work. The new results are presented in Section 3 and are discussed in Section 4. Related work is reviewed in Section 5, and conclusions are drawn in Section 6.

It is widely acknowledged within artificial evolution research that blind evolutionary search processes such as that implemented by the GA used here will frequently improve fitness via ruthless exploitation of any regularity in the task environment. We have seen that, although in the minority of the experiments reported here no such regularity was identified for exploitation, in the majority of our experiments there was an underlying regularity that allowed an evolved hybrid market mechanism to be more efficient. Thus, the major contribution of this paper is to demonstrate that, even when there are shock changes in supply and demand, there may be sufficient regularity in some market situations such that non-CDA hybrid two-sided auctions are more efficient than any human-designed market mechanism. Given these results, coupled with the results of Das et al. [11] who demonstrated that ZIP artificial trading agents reliably outperform human traders in experimental CDA settings, it seems plausible to conjecture that, in future, some or possibly all major financial markets will be implemented as e-marketplaces populated by autonomous software-agent traders. In such an agent-dominated future, market mechanisms originally designed for human traders may not be the most efficient; and the results of this paper demonstrate that new hybrid mechanisms can be evolved that are more efficient than traditional human-designed markets. Even if such hybrids are only a few percentage points more efficient than conventional human-designed mechanisms, it seems perfectly plausible that the results of using these artificially evolved auction-mechanism designs in major financial markets (populated by artificial trading agents) will be savings or profits measured in billions of dollars.