The Specker Derivative Game (SDG)

An Algorithmic Financial Derivative Trading Game

The game is dedicated to and named after my professor, co-advisor and first co-author: Ernst Specker from ETH Zurich who gave me Erdoes number 2 with a joint FOCS 1979 publication followed by a joint Journal of the ACM publication in 1981. Publications.

The Specker Derivative Game (SDG) is a game that invites us to deal with uncertainty. It is like with real financial derivatives: if you can predict the worst-case scenario for interest rates, exchange rates, future cost of goods or the weather, you can make a lot of money. It is similar with the SDG but the uncertainty can be controlled if one understands the nature of the game. SDG is a pure mental skill game such as chess. SDG has absolutely no element of chance whatsoever, with the winner solely determined by pure, unadulterated skill (there is a form of bad luck: that a derivative goes on sale and is too cheap, but it is not your turn to buy it). The game encourages the player to look at, understand, and experience things. It is a form of experiential learning in the Northeastern tradition. SDG teaches people lessons about themselves and the world, and allows such insights to be passed on to others.

A funny property of the game is that although it is about financial derivatives, it is indirectly also about mathematical derivatives that play a subsidiary role both to price the financial derivatives as well as to produce the finished product out of the raw material.

The purpose of the game is to explore an unknown territory of financial derivatives, to learn more about selling and buying such derivatives until one has the knowledge that guarantees that one will never lose in SDG. Opponents who don't have this knowledge will lose the game.

SDG Software Development Project

The game demonstrates how knowledge translates into superior performance and economic advantage. The game is very educational as a software development project and we use it at Northeastern for this purpose. The goal of the project is to create an algorithmic trader that sells and buys derivatives and that produces finished products out of raw materials. The algorithmic trader does not know the details of raw material when a derivative is bought. Only the "type" of the rawe material is known at that time.

Learning Units

In the first learning unit, the students learn about how to design data structures for the game, including representing the history of moves of a game. The second learning unit is to check whether a history conforms to the rules of the game. It is inherently easier to check a history than to play the game actively. Code developed here is useful during the game to check that the players conform to the rules. The third learning experience is to set up the rotating infrastructure for the game, abstracting from the details of the derivatives, the raw material and the finished product. This infrastructure could be used for other games. Then the infrastructure is specialized for SDG. This step involves defining interfaces that each program needs to obey. In which format are derivatives bought and sold? How is the raw material and the finished product represented? The fourth learning unit is to create an algorithm for producing raw material. Initially this can be accomplished by generating the raw material randomly. This might create raw materials that lose money but it is not a bad starting point. The fifth learning unit is to create an algorithm for finishing the raw material. Again a good starting point is an algorithm that uses randomness.

Now the automated trading algorithms are ready to play against each other and the hope is that by watching the game we can learn more about how to play the game well.

The rest of the project is to iteratively refine the raw material generator and the raw material finisher to make them better at playing the game.

Game Rules

The game has any number of players that take turns, always in the same sequence. The objects traded are financial derivatives. (Financial derivatives are financial instruments whose value derives from the value of assets underlying them. Examples of financial instruments used in derivative transactions are options. Options are financial instruments that convey the right, but not the obligation, to engage in a future transaction on some underlying security.) In each round, a player must offer at least one derivative for sale that is not for sale at the same or a lower price.

Each derivative has a type T and a creator and can be bought by a player at the price offered by the creator. All prices are real numbers in [0,1] (fraction of a million $). We say that a buyer owns a derivative. When you own a derivative of type T, you have the right to request raw material of type T and you have the right to sell back to the creator the product you produce from the raw material at a price that is equal to the quality of your product. The better quality you produce, the more you will be paid. On the other hand, the creator of the derivative has only the obligation to give you raw material of type T but he/she may make it hard for you to produce a high quality product.

What was left unspecified above was the concept of a type T of a derivative, the concept of raw material of type T and the concept of finishing the raw material with a certain quality. There are many ways to map those concepts, leading to different instantiations of the game. Below we present a simple mapping into the world of propositional logic.

Our raw material are Boolean formulas in conjunctive normal form (CNF). A CNF consists of a list of clauses. The same clause may appear several times: so our CNFs are a bag of clauses. Each clause consists of a list of distinct literals. A literal is either a positive or a negative variable.

raw material = CNF = bag of clauses

We need to define the concept of type of a CNF. The type of a CNF says what types of clauses the CNF contains. The type of a clause is a pair: the first element is the length of the clause (the number of literals) and the second element the number of positive literals. The clause (a !b !c) is of type (3,1) and the clause (!a !b !c !d) is of type (4,0). The type of a CNF is the union of the clause types. For example the CNF ((a) (b) (c) (!a !b) (!b !c)) is of type ((1,1) (2,0)).

We assume for now that clauses have at most 3 literals and that we have only two pairs in the type, for example ((1,1) (2,0)) or ((2,1) (3,0)). There are 2 types for clauses of length 1: (1,0) and (1,1). There are 3 types for clauses of length 2: (2,0), (2,1) and (2,2). There are 4 types for clauses of length 3. So there is a total of 9 types of clauses There are 4 types for clauses of length 3. So there is a total of 9 types of clauses. Therefore there are (9 choose 2) = 9*8/2 = 36 different pairs plus 9 single types. Therefore the game only has 45 different kinds of derivatives.

Note that because a clause like (a !b !b) is an illegal clause (because it contains non-distinct literals), the concept of type of a CNF tells us precisely what kind of clauses are in the CNF.

type of raw material = list of relations. Each relation is given by a pair of numbers.

The concept of finishing the raw material amounts to finding an assignment that satisfies many clauses (ideally it maximizes the number of satisfied clauses over all possible assignments). An assignment assigns true or false to each variable of a CNF. An assignment is represented by a clause: a positive literal means the variable is set to true, a negative literal means the variable is set to false. A clause is satisfied by an assignment if at least one literal in the clause is satisfied. A positive literal is satisfied if its variable is assigned true and a negative literal is satisfied if its variable is assigned false. The quality of an assignment is the fraction of satisfied clauses among the total number of clauses.

finished product = CNF plus assignment

The players rotate taking turns. A player's turn consists of four parts. They can be done in any order as the player chooses. In the first part, the derivatives that are on sale are searched and a decision is made which (if any) should be bought with the money available. The raw materials will be available for the bought derivatives in the next turn. In the second part, derivatives are put up for sale. They will be put at the end of the turn into the central store. Once a derivative is in the store, it will stay there until it is bought and finished or the game ends. However, if a player p drops out of the game because s/he is out of money or violated a game rule, the following happens: 1. Dervatives created by p are dropped from the store. 2. The money for derivatives bought from p but not yet finished is refunded to the buyer. (duplicated)

In the third part, raw materials are provided to all recent buyers. In the forth part, raw materials (connected to bought derivatives) are received from sellers, are finished and sold back to the sellers at the price determined by the quality of the finished raw materials.

It is explicitly allowed to create a derivative of type T and price p even if there is already a derivative of the same type T but with a higher price offered by some player.

If the derivatives are too expensive, nobody will buy them. For example, if all cost one (million). The rules of the game make the players either buy or create derivatives at a lower price than they are currently for sale by others: Here is an important rule:

When it is a player's turn: The player must buy at least one derivative from another player or re-offer all derivatives that are for sale by other players with a lower price than the current cheapest price for that derivative type.

The price of the cheapest derivative for a given type must be lowered by at least 0.01. Example: If a derivative was for sale at 0.63 million, the price must be lowered to at least 0.62 million.

This will create new derivatives of an existing type, one for each type that is currently for sale. In addition, a player may create new derivatives of new types. (The idea is that if a player does not want to buy, s/he must demonstrate that the prices are too high by lowering all of them. Several derivatives of the same type will be usually for sale and the clever buyer will normally choose the cheapest one.)

The game terminates after a fixed number of rounds (say 20). After that number of rounds nothing can be bought (or put on the market) but raw materials are still delivered and finished until all out standing obligations have been met. The winning player is the one who has the most money at the end of the game. Each player gets initially 5 million dollars.

If a player runs out of money, she loses the game immediately. This might happen if the player's derivative was bought and s/he does not have enough money to buy the finished product back. Therefore a player should not put cheaply priced derivatives on the market. A player also loses the game immediately when a rule of the game is violated.

When a player P loses the game, the administrator will refund all players who have not yet been paid for the finished product they delivered. The refund is the same as the original price for the derivative. When a player drops out, all the derivatives he offered for sale are no longer for sale.


We use an administrator ADMIN to control the game. Which means that we need to define how a player PL and ADMIN communicate. If we have n=3 players, PL1, PL2, PL3, timeslots are given to the players and the administrator in the following sequence: ADMIN PL1 ADMIN PL2 ADMIN PL3 ADMIN PL1 etc. until the game ends. This pattern generalizes to any number of players. The last activity will be by ADMIN because s/he terminates the game.

ADMIN keeps a central store of all derivatives that are for sale. Before it is PL's turn, ADMIN makes the list of derivatives that are for sale available to PL (for example in the central store or by sending them).

PL -> ADMIN messages

//put a given derivative into ADMIN's store

//when a player wants to buy a derivative

//PL sends raw material to ADMIN, then ADMIN sends it to the buyer
sendRawMaterial(Derivative, RawMaterial)

//PL sends the finished product to the ADMIN, then the ADMIN sends it to the producer
sendFinishedProduct(RawMaterial, FinishedProduct)

ADMIN -> PL messages

//what is for sale?

//when a buyer needs rawMaterial, s/he first sends a request to the ADMIN, who will send a request to the creator. This message is for requesting raw material from the creator.

requestFinishedProduct(Derivative, RawMaterial)

//this message is for sending rawMaterial to the buyer

//this message is for sending the finished product to the creator
sendFinishedProduct(RawMaterial, FinishedProduct)


Note that when you buy a derivative you buy it based on its type and its price. So you will need to figure out whether a price for a given type is fair. The uncertainty you have is different than with the weather, or exchange rates.

weather:  how nice will the weather be?
knowledge to reduce uncertainty: model of weather behavior.

interest rates:  how high will the rate be?
knowledge to reduce uncertainty: model of economy behavior.

Specker Derivative Game: how much can I satisfy in the CNF I get?
knowledge to reduce uncertainty: model of CNF satisfaction.

Transition System Specification

Basic Transitions: 
Offer: offer a derivative for sale
Buy: buy a derivative
Lower: lower the price of an existing derivative
DeliverR: Deliver raw material
Finish: Finish the raw material and sell back

For a player:
Finish* (Buy+ | Lower*) Offer+ DeliverR* 

After the final round: (to clear all rights and obligations)
Finish* DeliverR* 

Technical Requirements

Blackboard Organization.

The blackboard is the shared memory through which the players communicate. The communication of events happens through the store where all derivatives are centrally maintained. Only the administrator writes the store. The players express what they want to do, e.g., buy and sell, in file /playerName_done.xml. playerName must be of the form: FirstNameSoftwareDeveloper1_FirstNameSoftwareDevdeloper2 in alphabetical order, e.g., Kate_Sloan or Matt_Ryan.
blackboard/players/Matt.Ryan/any auxiliary file 

Configuration File.

The configuration file format is defined by the following "class dictionary". The blackboard path is an absolute path. The comment gives a typical value.
ConfigFile ="timeLimit" "="  int  // in seconds: 20 
"maxVars" "="  int // n = 10,max. number of variables in any raw material
"maxClauses" "="  int // n^3 + n^2 + n == 1110 
"maxWeight" "="  int // max. weight per clause, 100000
"maxTurns" "="  int // 20 
"blackBoardPath" "="  StringWithoutQuotes 
  // /home/your_login/csu670_blackboard or z:\\csu670game\\
"maxClauseLength" "="  int //3, max. number of clauses in raw material
"maxTypeLength" "="  int  //2 number of pairs in the type
"initialMoney" "="  float // in millions: 5.0 

Exchange Language.

The exchange language is defined by a class dictionary. It is an XML markup language. Interchange Language.

Player Invocation.

The player programs are called by the administrator. Each player gets a time slot determined by the configuration file. The player is not allowed to have any arguments. This means that it hardcodes the name of the configuration file config.dat and it may assume that this file exists in the player directory where the player program runs. The player directory is: blackBoardPath/players/playerName.

Operation of Administrator.

The administrator calles each player program when it is that player's turn. When the player writes the file: blackBoardPath/playerName_done.xml the administrator assumes that the player is done. If the player goes beyond the time limit, the administrator will remove the player from the game.

blackBoardPath/players.xml is created and updated by the administrator and contains information about who is still in the game and how much money they have.

The administrator processes the file playerName_done.xml, which contains a list of transactions as follows:

Buy: Update store field boughtBy. Update accounts of players.
Create: Add new derivative to store.
DeliverR: Update store field rawMaterial.
Finish:  Update store filed finishedProduct. Update accounts of players.
The administrator allows the players to deliver raw materials and finish products after the game is complete. One friendly way to implement this rule is that the administrator ignores all create/buy derivative transactions by the players.

A derivative remains in the store until an assignment has been generated for the derivative. Only then does the administrator remove the derivative from the store.

The administrator creates the history file by appending the transactions from the players to the file.

The administrator checks that when a player does not buy a derivative that the player creates sufficiently many new derivatives as required by the game rules.

Summary of Game rules

1. Raw material = weighted CNF.
2. Finished product = weighted CNF plus assignment.
2.1Quality of finished product = weighted fraction of satisfied clauses.
3. Minimal difference: the prices of derivatives of the same type must differ 
   by at least d_min. (Should be included in configuration file: currently
   d_min is 0.01.) Notice the crosscutting nature of this requirement.
4. A player is removed from the game when any of the game rules are violated.
5. A player must maintain a positive balance in the bank account.
6. If a player drops out of the game, bought but unfinished derivatives are refunded.
6.1If a player drops from the game, the derivates for sale by that player
   are no longer for sale.
7. When it is a player's turn: The player must buy at least one derivative 
   from another player or re-offer all derivatives that are for sale 
   by other players with a lower price than the 
   current cheapest price for that derivative type.
8. The game terminates after max_rounds rounds.
9. The winning player is the one with the most money in the bank account 
   at the end of the game.
10.A derivative can be bought only once.
11.Constants must be set as specified in the configuration file.
12.When a player P has bought a derivative, 
   the raw material will be available the next time it is P's turn.
13.When a player P has received the raw material for a derivative that P bought, 
   the finished product will be available the next time it is P's turn.

Feng's summary of game rules (checked by his administrator).

This list is better organized than mine.
1. Create Transaction
   Creator field of the derivative should be equal to Player's Name
   Name of the derivative should be unique
   If the type has been offered, the price must be strictly lower than 
   existing price
   The type of the derivative must conform to config.dat file.
    (e.g., for a pair(length,pos), pos<=length, pos>=0, 
   The price of the derivative must be <= 1.0 and >= 0.
2. Buy Transaction
   boughtBy field should be set properly
   The derivative should exist in the store and not be bought before.
   Players cannot buy their own derivatives.
3. Deliver Raw Material Transaction
   The original derivative must be in the store (the one w/o raw material).
   The creator is the player.
   The boughtBy field of the derivative must contain raw material.
   The raw material must match the type.
   The weight of each clause <= maxWeight. 
4. Finish Transaction
   The original derivative must be in the store.
   This derivative must have been bought by the player.
   The quality of the finished product must match the assignment.
5. Additional Rules
   If the player does not generate any Buy transaction, the player must
   re-offer all derivatives that are currently for sale by others
   at a lower price. (Only consider derivatives of different types. 
   If there are  several derivatives of the same type, only the lowest price counts.)

Karl J. Lieberherr, CCIS, Northeastern University, September-November 2007

For future versions: Require that during each round a player must create at least one derivative, either a derivative of a new type or a derivative of an existing type. In the latter case, the price must be lower than the current lowest price for a derivative of the same type. If a player does not buy and all types are used then the player will re-offer all derivatives for sale and will not reoffer a derivative twice.