8/8/89 Santa Fe Institute's D O U B L E A U C T I O N T O U R N A M E N T CHAPTER 1 -- INTRODUCTION ------------------------- This chapter describes the Double Auction (DA), including the specific conventions of the Santa Fe Institute's implementation. It provides an example of part of a game, raising some of the strategy issues. It also gives a broad overview of how the computerized tournament works, and a guide to the rest of the documentation. 1.1 Background -------------- The Double Auction (DA) is a type of trading institution used by the New York Stock Exchange, the Chicago Board of Options Exchange, and many other securities and commodity exchanges throughout the world. In the DA, buyers and sellers are simultaneously able to call out "bids" (offers to buy) and "offers" (offers to sell), or to accept the lowest outstanding offer or highest outstanding bid at any point in the trading process. The rapid flow of information combined with the ability of traders to undercut instantly any outstanding bid or offer makes the DA perhaps the closest embodiment of the economist's notion of a perfect frictionless market. The efficiency properties of these markets are legendary and have been extensively studied in laboratory experiments using human subjects (see surveys by Plott, 1982 and Smith, 1982a). In order to gain a deeper understanding of strategic choice in the DA, the Santa Fe Institute is sponsoring a computerized DA tournament. One goal of this tournament is to analyze the game when played by computerized trading strategies. To date, formal game-theoretic analysis of the dynamic DA game has not been forthcoming due to its inherent complexity. Thus insights gained into the nature of the decision processes actually employed in such situations could ultimately prove useful for improving our understanding of certain market phenomena such as the stock market crash in Fall 1987. Recent interest on Wall Street about the impact of computerized trading programs on market stability makes this analysis particularly timely. The inspiration for a computerized DA comes in part from Axelrod's (1984) "prisoner's dilemma" tournament. By allowing alternative algorithms to compete against one another, we can generate an easily controlled experimental environment. Within this environment, a variety of experiments can be performed on the submitted algorithms. This will allow us to evaluate carefully the important elements of each strategy, and to develop new insights into the game. A priori it is difficult to predict which strategies will perform well. Will complex strategies be more effective than simple ones? Can information about one's opponents be productively exploited? Are there strategies which can perform well in a variety of environments (for example, large versus small markets)? How will the strategies perform against human traders? Can the behavior of the computerized strategies be easily distinguished from human players? How well will the computerized double auction market operate? Will it result in highly efficient allocations as is observed in human DA markets? Will the market quickly stabilize at the competitive equilibrium allocations, or will instabilities such as market bubbles and crashes arise? To provide strong incentives for the submission of well developed strategies, prize money in the amount of $10,000 will be distributed among the participants. Payments will be proportional to the trading profits earned by the participant's strategy in the tournament. Algorithms are being solicited from individuals with a variety of backgrounds including business school students, computer scientists, economists, game theorists, learning theory specialists, and possibly even traders from real exchanges such as the New York Stock Exchange and the Chicago Board of Trade. It is our hope that these algorithms will embody a variety of strategic approaches, from simple, intuitive "rules-of-thumb" to sophisticated programs utilizing complex statistical, adaptive, and learning algorithms. The idea of running a Double Auction Tournament originated in the March, 1988 meeting of the Economy Program of the Santa Fe Institute. The original protocol was designed by Richard Palmer and John Rust. The experimental design of the tournament was developed jointly by John Miller, Palmer and Rust, with comments from Robert Axelrod, Charles Plott, Vernon Smith, and Shyam Sunder. A prototype version of the DA software was written in the Gauss programming language (for IBM PC's) by Rust in December, 1988. The software design is due to Palmer and Miller. The tournament software was written by Palmer (monitor, DANI, C and Fortran players) and Miller (Pascal players), with assistance and advice from Rust, Stephen Pope, and Michael Angerman. George Tsibouris and Palmer wrote the PC graphics routines using Turbo-C. The documentation was written by Palmer, with assistance from Miller and Rust. 1.2 The Computerized Double Auction ----------------------------------- The structure of our computerized DA game is very similar, but not identical, to the version of the DA used in laboratory experiments. The main differences are (1) time is divided into discrete BID-OFFER and BUY-SELL steps, and (2) the adoption of CHICAGO RULES, i.e. that only the current bidder and current offerer can accept the current offer and bid, respectively (these concepts are defined below). The time discretization was adopted to simplify the synchronization of communications in a multi-processing or network environment with delays that may vary from player to player or moment to moment. Chicago Rules were chosen to make our implementation of the DA resemble the new AURORA computerized DA market created by the Chicago Board of Trade. Having experimented with alternative sets of trading rules, we found that the Chicago Rules produce a "fairer", more strategically interesting version of DA without much random tie-breaking. The rest of this section describes the rules for our game: 1. Each player in a game is either a BUYER or SELLER of tokens. Players can specify which roles they are willing to play. They are all informed as to how many buyers and sellers there are in the game. In the tournament a program that can play both roles will play more games, and hence have more opportunity for profit, than one that can play only one role. 2. A game is divided into one or more ROUNDS. 3. Each round is divided into one or more PERIODS. 4. In each period, each buyer can buy up to N tokens and each seller can sell up to N tokens. A TOKEN can be thought of as a fictitious commodity that is being traded in the DA market. For simplicity, N is the same for all players and all periods in a game, and is between 1 and 4, inclusive. 5. For each round, each buyer is assigned N REDEMPTION VALUES, one for each token that could be bought. If the i'th token bought by a given buyer in a given period has redemption value R(i), and is bought at a price P(i), then that buyer makes profit R(i) - P(i) from the transaction. Thus buyers try to buy tokens as cheaply as possible below their redemption values. Redemption values are given in decreasing order, and are assumed to be used in that order since it maximizes profit. 6. For each round, each seller is assigned N TOKEN COSTS, one for each token that could be sold. If the i'th token sold by a given seller in a given period has token cost C(i), and is sold at a price P(i), then that seller makes profit P(i) - C(i) from the transaction. Thus sellers try sell tokens for as much as possible above their token costs. Token costs are given in increasing order, and are assumed to be used in that order since it maximizes profit. 7. Redemption values and token costs in general are different for each player, and are private information not communicated to other players. 8. Note that redemption values and token costs are the same for each period within a round, but in general differ from round to round. During a given round, strategies may be able to benefit from information gathered about opponents' redemption values or token costs in previous periods. 9. Each period consists of a number of alternating BID-OFFER steps and BUY-SELL steps, starting with a bid-offer step. 10. In a bid-offer step each buyer who has not already bought N tokens in that period may make a bid to buy one token. The buyer specifies the price of the bid; prices must be integers. If there is already a current bid (see below) the price must be higher than the current bid price. 11. In a bid-offer step each seller who has not already sold N tokens in that period may make an offer to sell one token. The seller specifies the price of the offer; prices must be integers. If there is already a current offer (see below) the price must be lower than the current offer price. 12. At the conclusion of a bid-offer step, the highest bid made becomes the CURRENT BID, and the lowest offer made becomes the CURRENT OFFER. If no new bids were made the previous current bid remains if there was one; otherwise there is no current bid. Similarly for offers. Any ties for highest bid or lowest offer are broken randomly. 13. All players are informed about all legal bids and offers, and who made them, at the conclusion of each bid-offer step. At all times they know the current bid and offer (if any), and who holds them -- the CURRENT BIDDER and CURRENT OFFERER. 14. In a buy-sell step, one or more buyers may ask to accept the current offer; this is a BUY request (see also rule 15). Similarly one or more sellers may ask to accept the current bid; this is a SELL request (see also rule 16). If more than one request occurs, one is selected randomly; only one transaction (either a buy or a sell) can occur in each buy-sell step. 15. If there is a current bid, then only the current bidder is eligible to make a buy request. If there is no current bid, then any buyer who has not already bought N tokens in this period may make a buy request. 16. If there is a current offer, then only the current offerer is eligible to make a sell request. If there is no current offer, then any seller who has not already sold N tokens in this period may make a sell request. 17. When a transaction occurs the transaction price is equal to either the current offer (if a buy request was accepted), or to the current bid (if a sell request was accepted). Both the buyer and seller involved receive profit as described above (see rules 5 and 6), and consume one of their N tokens. 18. All players are informed about all transactions that occur. The information consists of the transaction price, the identity of the buyer and seller involved, and whether it was a buy or a sell request that was accepted. They are not informed about other buy or sell requests that were not accepted. 19. If a transaction occurs in a buy-sell step, then both the current bid and the current offer are cleared before the next bid-offer step. Otherwise they are retained. 1.3 An Example -------------- A simple example will serve to clarify the above definition of the game, and to raise some of the strategy issues. We focus on a single seller S1 in a game with three buyers (B1, B2, and B3) and three sellers (S1, S2, and S3). We consider only the first few steps of one period of the game. Our seller S1 was assigned four tokens with the following token costs for the round we are examining: 100 200 300 400 The first few steps are shown in the following table, in a format based on the monitor's listfile display (see the "monitor" chapter of the documentation for full details), constituting the information available to S1. The left-hand columns show the time and step type (BO = bid-offer, BS = buy-sell). The right-hand columns show the current bid and current offer after each step, and the price of each transaction that occurs. The participants in a transaction are shown by >'s (for a sell) or <'s (for a buy). |t | B1 B2 B3 | S1 S2 S3 | cbid coff price| +-------+-------------------+-------------------+----------------+ |1 BO | 50 75* 60 | 410* 500 450 | 75 410 | | BS| | | 75 410 | |2 BO | 100 85 130* | 350 330* 400 | 130 330 | | BS| | | 130 330 | |3 BO | 150 140 175* | 250* 275 320 | 175 250 | | BS| > | > | 175 | |4 BO | 80* 80 60 | 400 405 250* | 80 250 | | BS| | | 80 250 | |5 BO | 125* 100 110 | 225* 230 240 | 125 225 | | BS| | | 125 225 | |6 BO | 150 180* | 215 200* 215 | 180 200 | | BS| < | < | 200 | BID-OFFER STEP 1: The period begins, and our seller is called on to make an offer. She has no information about the other players, and can only judge an appropriate offer value by looking at her own token costs (100, 200, 300, 400). She could do nothing, and see what the others do, but she decides to make an offer of 410. If accepted this would yield her a profit of 410 - 100 = 310. Her offer turns out to be the lowest among the three sellers (see the table) and so becomes the current offer. On the buyer's side the highest bid was 75, which thus becomes the current bid. The current bid and current offer are marked by asterisks (*) in the table. BUY-SELL STEP 1: Because she is the current offerer, our seller is now eligible to make a sell request, to sell her first token to the current bidder (B2) at the current bid price of 75. But that would be foolish; she would make a loss of 25. So she does nothing. The current bidder also has the option of making a buy request, to buy a token from our seller at her current offer price of 410. She'd be happy if he did so (giving her 310 in profit), but he doesn't. This illustrates a general feature of the buy-sell step. It can be thought of as a two-person game between the current bidder and the current offerer, and each hopes that the other will accept. Besides locking in a profit, the incentive to make a buy or sell request oneself is mainly not to have to play another bid-offer step, with the consequent risk of losing the bidding or offering lead. There may also be an incentive to make a trade before time runs out towards the end of a period. BID-OFFER STEP 2 Given that her outstanding current offer of 410 was not accepted, our seller decides to lower her offer to 350. Here she must strike a balance between going too low, and thus losing potential profit, and not going low enough to win the current offer. Ideally she would guess the best offer of the other sellers, and then go just below it (assuming she could still make a profit). As it is, she doesn't go low enough; seller S2 beats her with an offer of 330. The current bid for the buyers increases to 130. The bid-offer step can be thought of as an n-person game between the n buyers, and an m-person game between the m sellers. Actually it may not always be advantageous to win the bidding. One strategy is to "hang behind" the leaders until a transaction seems imminent, and then to jump in just ahead of the competition. But this requires good knowledge of the others' probable behavior. BUY-SELL STEP 2 Again no transaction occurs. In fact this is the normal state of affairs; there are typically far more steps in a period than there are tokens to be traded, so transactions occur relatively infrequently. One strategy is to make a buy or sell request as soon as a "reasonable" profit can be made, before "all the best buys are gone". Though this may give early profit in a game, it does not necessarily make the most profit; holding out for a better price may do better. BID-OFFER STEP 3 Our seller goes down to 250 and again gets the lead. Meanwhile the buyers come up to 175. BUY-SELL STEP 3 Our seller again has a chance to request a sell, and this time she chooses to do so. It is accepted and she has made a profit of 175 - 100 = 75. We don't know whether the current bidder B3 made a simultaneous buy request; if he did there was a random draw, which S1 must have "won". This is a random draw it is not good to win; if B3 had won the draw the transaction price would have been 250 instead of 175, actually doubling our seller's profit. BID-OFFER STEP 4 Because a transaction occurred, the current bid and offer have been removed (see the right-hand columns). So now S1 can make any bid she likes. One strategy here is to jump close to the previous transaction price; another is to start far away and work slowly back towards it. The latter gives more information, and is perhaps more likely to convince the buyers to accept a higher price, but is thwarted by just one seller employing the "let's get right back near the last price" approach. Our seller decides to make a high offer of 400. But S3 jumps in with a much lower offer, at 250. Note that on the buyer's side there was a tie for the current bid, and B1 was randomly chosen. BUY-SELL STEP 4 No transaction occurs. BID-OFFER STEP 5 Our seller now has a rather limited range in which to make a new offer; she must go below the current offer of 250, but obviously wants to stay above her next token cost of 200 (recall that she sold her first token, and is now onto her second). She splits the difference at 225, and wins the current bid. BUY-SELL STEP 5 No transaction occurs. Our seller is eligible to accept the current bid of 125, but would make a loss if she did so. BID-OFFER STEP 6 S1 is pinned between 200 and 225. She tries 215, but is beaten by S2 at 200. Note that now there is nothing she can do until after a transaction occurs; the current offer is too low for her to beat with any hope of profit. Notice that B2 didn't make a bid on this step. This may signify that he cannot do so profitably, but may also represent a wait-and-see approach. It could also be that he didn't respond in time or encountered an error. Watching where other players stop bidding or offering often gives valuable information, but must be interpreted carefully. Bluffing (by sticking at one price, even though it may not be close to the token value) is certainly possible. BUY-SELL STEP 6 B3 accepts S2's offer and a second transaction occurs. There was a range of only 20 points between the current bid and offer at this point. Patient players might have continued for several more steps, with the prices edging together, before concluding a transaction. As the prices come together, either player can gain more profit by accepting, but both risk losing the bidding/offering lead to other players. We leave the detailed example at this point. Several more transactions would probably occur during this period. Then the next period would begin, with everyone having the same token values. In this new period our seller might base her offers and sell requests on information gained in the previous period. She might also want to use some of the information she ignored during the first period, including the actual bids and offers (whether accepted or not) made by each of her opponents during the actual play, the transaction prices for the trades that did occur, and so on. She might also be able to develop a sense of how her opponents are likely to respond (such as the observation that S3 always seems to offer 10 points below the previous current offer value when there was one). This sort of information might even be useful in another round, where the opponents are the same even though the token values are different. One of the best ways to understand the rules of the game, as well as to gain insights into potential strategies, is to actually play some games against a set of sample strategies. This can be done either on the Santa Fe Token Exchange or entirely on a local computer, as described below and in the rest of the documentation. 1.4 Implementation of the Computerized Double Auction ----------------------------------------------------- The Santa Fe Institute's implementation of a computerized double auction is based on two principles: 1. The players in a game are represented by separate independent programs. This allows easy development of players in a diverse set of languages on a variety of machines, and makes it easy to construct games between selected subsets of available players. 2. Participants developing strategies only need to understand and work with programming details related to strategy, not with control, communications, book-keeping, synchronization, etc. (This is almost but not quite true.) Principle (1) is realized by having a separate MONITOR PROGRAM that manages the game. The players and the monitor are all separate programs. The monitor is NOT an auctioneer; it only serves to coordinate message-passing between the separate player programs. Thus, all programs communicate only with the monitor, but not directly with each other. There are various communication methods that can be used, though not all are available on all systems; these are discussed in detail in chapter 2, Software. Depending on the system, the monitor and players may all be on the same machine, or may be distributed on a network. At present networking is possible only for TCP/IP communications on the Internet network. Local players (on the same CPU as the monitor) are normally started up and controlled by the monitor, according to a list in the "players file". Network players are started up separately after the monitor is running, and then connect to the monitor. A networking monitor running regularly at Santa Fe (every hour on the hour) forms the Santa Fe Token Exchange (SFTE). Participants with TCP/IP access to the Internet can play practice games with the SFTE across the network. Results are mailed back to them automatically. But even if they can use the SFTE, most participants will want to set up a monitor running on their own computer too. Principle (2) is realized by the provision of "skeleton" player programs in C, Fortran, and Pascal. These programs will run as they are, playing the Double Auction according to a simple strategy. The strategic parts of these programs are well separated from the control and communications parts, so that participants can easily identify the routines they need to modify to implement their own strategy. They should not need to understand the control and communications parts at all. In all three languages a standard set of variables specifies the state of the game, and standard routines are called to request strategic decisions. For example, in a program playing a buyer, a routine called "bid" is called in each bid-offer step and must return the value of the bid to be made (or 0 for none). Within the "bid" routine the current status of the game, and some cumulated history, is available for reference in making the decision. Chapter 3, The Skeleton Programs, describes the variables and routines in detail. The initial stages of setting up the Double Auction on a new machine may take a little time, and might in some cases require help from the organizers. But once a monitor and the skeleton programs are running, actual development of a strategy should be simple (at least from a programming standpoint) and can entirely ignore all the communication and control issues. A special player program called the "human player" provides an interface so that participants can themselves play a game against computer players. This may be done both on the SFTE and with a monitor running locally. The monitor, skeleton players, and associated support software have been tested and debugged on a variety of machines and systems including: Unix systems (BSD and System V) IBM PC's and compatibles Vax/VMS Cray/Unicos The organizers will advise on porting the software to further systems, and will help with it when appropriate. Note that porting to a Macintosh is NOT possible, due to operating system limitations. All the software is available from the Santa Fe Institute, via electronic file transfer (anonymous ftp or electronic mail), or on floppy disks. Chapter 2, The Software, gives detailed instructions for obtaining it. Knowledgeable ftp users can look directly in pub/dat by anonymous ftp at sfi.santafe.edu; the README file contains a description of the files. The documentation itself is also available in electronic form, or can be obtained in printed form from Santa Fe. A small charge is made for sending disks or printed documentation from Santa Fe. The software itself is free except for that required to set up a networking monitor other than the SFTE; this is not normally distributed (in part to encourage use of a single network token exchange), but may be sold and licensed on request. The actual tournaments will be conducted at Santa Fe, not over the network. Participants will submit the source of their player programs, or at least the strategic subroutines from those programs. The "rules" chapter of the documentation contains details. 1.5 Electronic Mailing List --------------------------- An automatic electronic mailing list is maintained at the Santa Fe Institute for discussions and announcements relating to the Double Auction Tournament. You will be added to the list when you make an initial enquiry about the project, or if you ask specifically to be added. All mail sent to the e-mail address dat-list@sfi.santafe.edu will be sent on automatically to everyone on the mailing list. The list is unmediated, so please be polite, concise, and considerate. The DAT organizers are themselves on the list and will respond as appropriate to queries mailed to the list. Individual queries not of general interest should be mailed to dat, not to dat-list. For additions, deletions, and changes to the list, please send mail to dat@sfi.santafe.edu or dat-list-request@sfi.santafe.edu but NOT to the list itself. All correspondence sent to the mailing list is appended to the file "mail" in the pub/dat directory accessible by anonymous ftp at sfi.santafe.edu. See Chapter 2 (software) for more information about ftp. 1.6 Documentation ----------------- The documentation for the Double Auction Tournament is divided into a number of different chapters. You will not necessarily need all of these. The name shown in parentheses after each heading below is the file name for that chapter in the electronic form of the documentation. 0. Title Page (title) 0.1 Title 0.2 Authors 0.3 Abstract 0.4 Table of Contents 0.5 Acknowledgements. 1. Introduction (intro) [This chapter] 1.1 Background 1.2 The Computerized Double Auction -- Game rules 1.3 An Example, with comments on strategy 1.4 Outline of software implementation 1.5 Electronic Mailing List 1.6 Documentation summary. 2. Software (software) 2.1 Communication methods 2.2 Outline of available software 2.3 Obtaining the software and documentation 2.4 Getting started 2.5 Getting help 3. Skeleton Programs (skeleton) 3.1 Introduction 3.2 Variables in the user routines 3.3 Working variables 3.4 Return values 4. The monitor (monitor) 4.1 Starting the monitor 4.2 Runtime commands 4.3 Vax/VMS notes 4.4 Explanation of listfile output 4.5 Explanation of logfile output 5. The player programs (players) 5.1 Starting the player programs 5.2 Explanation of human player and C-player output. 5.3 Prompts and responses in the human player. 5.4 History display in the human player. 6. DANI (dani) [see Note 1] 6.1 Communication methods 6.2 Starting DANI 6.3 Vax/VMS notes 6.4 Explanation of display output 7. Tournament rules (rules) 7.1 Rules for entries 7.2 Registration form 8. Message passing protocol (messages) [see Note 2] 8.1 Messages and message packets 8.2 Order of packets 8.3 Individual Steps of DA game 8.4 Special messages 8.5 Summary 8.6 Code table 9. References (refs) 9.1 References The text of the poster is also available, in file 'poster'. Permission is hereby granted to post this poster, without substantive change, to any bulletin board or news group. Note 1: The description of DANI in chapter 6 is only needed if you want to use a language other than C and use the SFTE via the Internet. Note 2: Chapter 8 is a technical document on the messages passed between monitor and players. It is NOT needed for ordinary participants who base their players on the skeleton programs.