                                                                     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.
