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 <dat@sfi.santafe.edu>
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.
