Topic: Trading/order fulfilling algorithms (Read 1258 times)

Keep in mind that these orders don't all appear at once. They happen sequentially and are generally resolved according to the terms of the earlier order.


On the other hand, the Gemini exchange has a particular kind of auction in which all orders are resolved simultaneously. Here is how it works according to them:


This page goes into a little more detail: https://gemini.com/marketplace/#gemini-auction-example

You might have a look at davout's website code, if you like ruby.

I have also been thinking about that for a few weeks now.  I'm working on yet-another implementation in bash.

The problem with this kind of stuff is, as you pointed out, it's easy to make a simple implementation but much more complex if you want to make it optimal.

I can't believe there is not more public documentation about these kinds of algorithms.

Hey,

I've tried google but it's not turning up much. I'm looking for algorithms to match up and fulfill an orderbook.

A offers 20 GBP for 10 BTC
B offers 5 BTC for 9 GBP
C offers 2 BTC for 6 GBP

Looking above we can see that to fulfill A's order, we can use B but not C's order:

BTC per GBP for A = A_want / A_amount = 10 / 20 = 0.5
BTC per GBP for B = B_amount / B_want = 5 / 9 = 0.56

if B_amount / B_want >= A_want / A_amount
(rephrased to avoid float rounding errors)
if B_amount * A_amount >= B_want * A_want
then order is OK

So using B's rate to fulfill A's order gives A more BTC for his GBP's worth:

=> take B's order from A leaves:
A offers 11 GBP for 5.5 BTC at the original rate of 0.5  (A got a better deal than he was asking for but the rate he has chosen remains fixed).

Do the comparison for C we see that (2 * 11 = 22) < 6 * 5.5... Ergo C's order is invalid for A.

HOWEVER

This isn't optimal at all. It has two problems:
- The rate is fixed at what A has chosen.
- Doesn't find the best all round solution to fulfill an order for everybody.
I tried rephrasing it as a linear programming problem,

A offers 20 GBP for 10 BTC
B offers 5 BTC for 9 GBP

x = X / GBP
y = Y / BTC

Constraints:
x <= 20
y <= 5

y >= x * 10 / 20  (from A's order)
or y >= 0.5 x

x >= y * 9 / 5     (from B's order)
or y >= 0.56 x

I have to maximise x + y in the space between those 2 lines and the box from the first 2 constraints... However the problem becomes error prone fast- I can easily do bounds detection but am worried about bugs.

Implementation MUST be perfect. Therefore I'm asking if anybody knows any pre-existing systems, algorithms or code I can read.