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.
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.
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.
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.
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).
//put a given derivative into ADMIN's store
putInStore(Derivative)
//when a player wants to buy a derivative
buyFromStore(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)
//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.
requestRawMaterial(Derivative)
//
requestFinishedProduct(Derivative, RawMaterial)
//this message is for sending rawMaterial to the buyer
sendRawMaterial(Derivative)
//this message is for sending the finished product to the creator
sendFinishedProduct(RawMaterial, FinishedProduct)
uncertainty ----------- 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 Sequence: For a player: Finish* (Buy+ | Lower*) Offer+ DeliverR* After the final round: (to clear all rights and obligations) Finish* DeliverR*
blackboard/ blackboard/store.xml blackboard/players.xml blackboard/playerName_done.xml blackboard/history.xml blackboard/config.dat blackboard/players/Matt.Ryan blackboard/players/Matt.Ryan/Matt.Ryan.jar blackboard/players/Matt.Ryan/somelibrary.jar blackboard/players/Matt.Ryan/any auxiliary file blackboard/players/Jason.Morgan blackboard/players/Jason.Morgan/Jason.Morgan.exe blackboard/players/Jason.Morgan/Jason.Morgan.dll
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
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.
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.
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,
length<=maxClauseLength)
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.