Trading Robots: The Specker Derivative Game (SDG)

Experientially Learning Computer Science Through a Game of Derivative Trading Robots

In the Specker Derivative Game the robots (algorithmic players) deal with three concepts: (financial) derivatives, raw materials corresponding to a derivative and finished products with their quality produced from the raw materials. The game is about offering and selling/buying derivatives and maximizing the profit. Each derivative consists of a type (partial information about raw material) and a price. Raw materials are produced by the seller of a derivative AFTER it is sold and the type of the raw materials must match the type of the derivative. The buyer finishes the raw materials and the seller is obliged to buy back the finished product at a price determined by the quality of the finished product (hence the term derivative). The game is quite general and applies to buying and selling generative, active participation products based on partial information (the type).

The game is parameterized by a triple (R,T,F) of raw materials (R) and their types (T) and finished products (F) produced from the raw materials.

The game invites the algorithmic player implementors (students) to experiment with a wide variety of skills at different levels of abstraction. The game is an excellent abstract thinking device because insights the students have are not directly applied to playing the game, but are abstracted into a strategy that is expressed in their program. The game is quite general and applies to buying and selling generative, active participation products based on partial information (the type). The students go through a learning cycle starting from getting the basic game rules implemented correctly to improving the strategies used by the various agents, like the raw material construction agent or the product finishing agent.

• At the first level, they need to flesh out the requirements and decide on a game infrastructure either using a distributed network of players with a publish-subscribe capability or using a centralized administrator aloting a time interval to each player and maintaining a centralized store of derivatives.
• After the basic mechanics of the game are worked out, the students think about how their players should price derivatives, when they should buy a derivative, and how they should produce raw materials. At this level their reasoning is looking for heuristics to use, like "when I buy from this player, I always make money, so I should probably buy more from the same player".
• After this simple heuristics phase, students focus on a system analysis of the game which focuses on precise questions like "what is the lowest price at which I can offer this derivative without losing money"? This leads to a much better understanding of the "economy" behind SDG but it requires solving min-max problems. This leads to the study of numerous algorithms for minimizing and maximizing functions, and more specific algorithms like computing Fibonacci numbers, etc.

As with any game, once it has been figured out how to play the game perfectly, it becomes boring. The fun is in figuring out how to improve the algorithmic players; the game is only fun while learning takes place. The path to the best algorithmic players is at least as important as the final outcome. The game is about experiential learning in the tradition of Northeastern.

Here is a simple instantiation of the game suitable to teach topics like: Software Development (from Requirements to Implementation), Discrete Mathematics (Propositional logic, combinations and permutations, minimizing and maximizing quotients of polynomials, solving min-max problems, mathematical problem solving techniques), Algorithms (solving recurrence relations, dynamic programming, DPLL algorithms, etc.), complexity theory (the optimal price for a derivative "separates" P from NP).

R = CNF (conjunctive normal form = a set of weighted clauses); T = the set of clause types used by the cnf; F = an assignment to the cnf. The quality of a finished product is the weighted fraction of satisfied clauses. The type T0 = {R1,R2} uses only two clause types: R1(a) = a, R2(a,b) = !a or !b. The lowest price p at which the derivative (T0,p) can be offered without losing money is (sqrt(5)-1)/2 = 0.618... The raw material construction for this derivative involves the Fibonacci numbers. The finishing process involves solving an NP-complete problem but it turns out that if the players play rationally, the problem is not NP-complete.

There are many interesting instantiations of the SDG idea. We have experienced a few pointed to by the SDG Home page.

What real algorithmic players do: Algorithmic Trading | Conference on Game Development in Computer Science.

Acknowledgements: The SDG game was inspired by a collaboration with GMO.