Return-Path: Delivery-Date: Mon, 17 Jul 89 14:02:22 PDT >From dat@sfi.santafe.edu Mon Jul 17 14:02:11 1989 Received: by gilroy.pa.dec.com (5.57/4.7.34) id AA14198; Mon, 17 Jul 89 14:02:11 PDT Received: from SFI.SANTAFE.EDU by decwrl.dec.com (5.54.5/4.7.34) id AA15638; Mon, 17 Jul 89 14:00:00 PDT Received: from SFI.SANTAFE.EDU by decwrl.dec.com (5.54.5/4.7.34) for hibbert@gilroy; id AA15638; Mon, 17 Jul 89 14:00:00 PDT Received: by sfi.santafe.edu (5.59++/IDA-1.2.8) id AA08992; Mon, 17 Jul 89 14:55:49 MDT Message-Id: <8907172055.AA08992@sfi.santafe.edu> Date: Mon, 17 Jul 89 14:55:49 MDT From: Double Auction Tournament To: blee@grads.cs.ubc.ca, csinger@cs.ubc.ca, finholt@andrew.cmu.edu, hibbert@wsl.dec.com, mdixon@arisia.xerox.com, phkoo@rhodes.bellcore.com, schang@gte.com, zhang@cs.ubc.ca Subject: Double Auction Tournament Thank you for your inquiry about Santa Fe Institute's Double Auction Tournament. Following this preface is the first chapter of the documentation for the tournament. If after reading this you are still interested in the project you should next get the second chapter, called "The Software". This contains a description of all the software and explains how to get it and the rest of the documentation. You can get the second chapter by either of the following methods: 1. Request from dat@sfi.santafe.edu that it be sent by electronic mail. 2. Get it yourself from sfi.santafe.edu by anonymous ftp (all the software and documentation is available this way). If you have the standard ftp you need the following commands: ftp sfi.santafe.edu (or ftp 192.12.12.1) specify user name as: anonymous specify password as your own name cd pub cd dat cd doc get software quit This should create a file called 'software' in your current directory. ------------------------------------------------------------------------------ 7/12/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, 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. 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 1988. 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? Will market bubbles and crashes occur? 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 seasoned traders from the New York Stock Exchange and the Chicago Options Exchange. It is our hope that these algorithms will embody a variety of strategic approaches, from simple rule-of-thumb procedures to programs utilizing complex statistical, adaptive, and learning algorithms. 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) that time is divided into discrete steps of two alternating types, and (2) that only the holders of the current bid and offer can accept the current offer and bid (respectively). (1) is needed for the multi-processing network environment of the game, to eliminate the effect of processor and network delays. (2) was chosen to make the game more like that used for trading on the Chicago Board of Options Exchange, and to make a strategically more interesting game with little need for 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. 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, as described below. N is the same for all players and all periods in a game, and is normally either 1 or 4. 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 Ri, and is bought at a price Pi, then that buyer makes profit Ri - Pi 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 must be used in that order (which 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 Ci, and is sold at a price Pi, then that seller makes profit Pi - Ci 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 must be used in that order (which 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 of 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 during consecutive 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 a 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 a offer to sell a 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. Similarly one or more sellers may ask to accept the current bid; this is a "sell" request. 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, 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. 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), but only showing 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 handsome 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 is normally a two-person game between the current bidder and the current offerer, and each hopes that the other will accept. 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. 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. In general the bid-offer step involves 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. An interesting 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 rarely. A common beginner's 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 twarted by just one seller employing the "let's get right back to a sensible price" approach. Our seller decides on the conservative approach, making the high offer of 400. Unfortunately 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 on to 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. This would have have yielded a better price for both the buyer and the seller who made the final transaction, but a particular buyer or seller would risk losing the lead and thus all the profit in the sale. 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. 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 player programs each communicate 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 the "software" chapter of the documentation. 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. The "skeleton" chapter of the documentation 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 programmimg 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. The "software" chapter of the documentation gives detailed instructions for obtaining it. Knowledgable 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. 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) Title. Authors. Abstract. Table of Contents. Acknowledgements. 1. Introduction (intro) [This chapter] The Double Auction. Game rules. Example, with comments on strategy. Outline of software implementation. Documentation summary. 2. Software (software) Communication methods. Outline of available software. How to get the software and documentation. Getting started. Getting help. 3. Skeleton Programs (skeleton) Structure of the programs. Strategy routines and miscellaneous routines. Variables available. Return values. 4. The monitor (monitor) Starting the monitor. Arguments and options. Runtime commands. Explanation of listfile and logfile output. 5. The player programs (players) Starting the players. Explanation of human player and C-player output. Prompts, responses, and history display for human player. 6. DANI (dani) [Note: This describes the Double Auction Network Interface, which is only needed if you want to use a language other than C and use the SFTE via the Internet.] Communication methods. Starting DANI. Explanation of output. 7. Tournament rules (rules) Rules for entries. Parameter settings for tournament games. Registration form. 8. Message passing protocol (messages) [Note: This 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.] Messages and message packets. Order of packets. Individual steps. Special messages. Code table. 9. References (refs) References and Bibliography. 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.